Грани и рёбра в графе

[Hasek]

Во всех найденных доказательствах непланарности $K_{3,3}$ используется то, что любая грань ограничена не менее чем четырьмя рёбрами. Почему так? Ведь при взгляде на рисунок сразу видны и треугольные грани, ограниченные лишь тремя отрезками рёбер.

[Slav-27]

Если бы эту штуку можно было нарисовать на плоскости без пересечений рёбер -- вот тогда была бы

Hasek в сообщении #1152405 писал(а):

любая грань ограничена не менее чем четырьмя рёбрами

-- потому что рёбра, которые ограничивают грань, образуют цикл.

[Hasek]

Благодарю, понял. Зря я пытался осознать это на заведомо неподходящей картинке (ведь граф предполагается планарным в доказательстве от противного).

[svv]

Hasek в сообщении #1152405 писал(а):

Ведь при взгляде на рисунок сразу видны и треугольные грани, ограниченные лишь тремя отрезками рёбер.

«Отрезками» не считается. Настоящая треугольная грань имела бы рёбра, соединяющие вершины одного цвета, чего в данном графе нет.