Теорема 2: Графы и , где множество состоит из элементов вида , не допускают плоской реализации
Доказательство: Отметим, что в графе нет циклов длины 3, так как любое ребро ведет из группы вершин в группу . Любой цикл на графе имеет, поэтому, длину большую или равную четырем. Предположим теперь, что допускает плоскую реализацию, тогда для чисел получаем равенства , а из условия следует .
Пусть — число ребер, ограничивающих грань с номером ; имеем и , то есть . Полученное противоречие доказывает первую часть теоремы.
Допустим, что допускает плоскую реализацию. Тогда из теоремы 1 имеем равенства: .
Пусть имеют тот же смысл, что и раньше. Очевидно, и поэтому выполнено неравенство: .
Доказанная теорема допускает обращение. Это значит, что она представляет доказательство необходимости в следующем критерии, позволяющем решить вопрос о том, допускает ли граф плоскую реализацию.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление