Мотивировка теоремы Куратовского

[gogoshik]

Помогите, плиз, разобраться зачем нужна теорема (критерий) Куратовского с её такой "необычной" формулировкой?

The Theorem (Kuratowski). A graph is planar if and only if it does not contain a subgraph homeomorphic to $K_{5}$ or to $K_{3,3}$.

Я о том, что для того чтобы проверить планарность графа можно воспользоваться более простым критерием на основе формулы Эйлера: $e \leqslant 3v - 6$, где $e$ -- число ребер, $v$ -- число вершин графа. Задан граф, считаем число ребер и вершин, подставляем в неравенство. Если условие выполняется -- граф планарен, иначе нет. Делов то

[Pphantom]

gogoshik в сообщении #1354299 писал(а):

Я о том, что для того чтобы проверить планарность графа можно воспользоваться более простым критерием на основе формулы Эйлера: $e \leqslant 3v - 6$, где $e$ -- число ребер, $v$ -- число вершин графа. Задан граф, считаем число ребер и вершин, подставляем в неравенство. Если условие выполняется -- граф планарен, иначе нет. Делов то

Ниже изображен т.н. "граф Петерсена". Проверьте, удовлетворяет ли он вашему критерию. Ну а потом попробуйте привести его к планарному виду.

[Someone]

Да и граф $K_{3,3}$ удовлетворяет неравенству $e\leqslant 3v-6$.

[Pphantom]

Угу. Но есть известное высказывание (кажется, Дональда Кнута) на эту тему. Дословно не помню, но смысл примерно такой: "если вам кажется, что вы сформулировали какое-то новое утверждение в теории графов, проверьте его для графа Петерсена, обычно этого оказывается достаточно, чтобы понять, что вы ошиблись".

[Someone]

Pphantom, я имел в виду, что gogoshik мог бы проверить своё утверждение прямо на тех двух графах, которые упоминаются в ненужной по его мнению теореме. Никаких возражений против графа Петерсена у меня нет.

[sqribner48]

Пока писал появились сообщения от Someone и Pphantom
Как говорится, добавлю свою "лепту" к их замечаниям.
gogoshik
Неравенство $e \leqslant 3v -6$, являющееся следствием из формулы Эйлера для полиэдров (теорема 11.1), есть необходимое условие планарности графа в терминах числа ребер.

Цитата:

см. книгу Харари "Теория графов" стр. 128.
Следствие 11.1 (в). Если $G$ — произвольный планарный $(p,q)$-граф и $p \geqslant 3$, то $q\leqslant 3p-6$. Если граф $G$ двусвязен и не содержит треугольников, то $q \leqslant 2p-4$.

А теорема Куратовского дает необходимое и достаточное условия планарности графа.
Именно об этом намекнули уважаемые Someone и Pphantom