Теорема 2: Графы и , где множество состоит из элементов вида , не допускают плоской реализации

Доказательство: Отметим, что в графе нет циклов длины 3, так как любое ребро ведет из группы вершин в группу . Любой цикл на графе имеет, поэтому, длину большую или равную четырем. Предположим теперь, что допускает плоскую реализацию, тогда для чисел получаем равенства , а из условия следует .

Пусть — число ребер, ограничивающих грань с номером ; имеем и , то есть . Полученное противоречие доказывает первую часть теоремы.

Допустим, что допускает плоскую реализацию. Тогда из теоремы 1 имеем равенства: .

Пусть имеют тот же смысл, что и раньше. Очевидно, и поэтому выполнено неравенство: .

Доказанная теорема допускает обращение. Это значит, что она представляет доказательство необходимости в следующем критерии, позволяющем решить вопрос о том, допускает ли граф плоскую реализацию.

Дата добавления: 2014-01-03