2015-06-28
1622
ТЕОРЕМА. Графы К3.3 и К5 не допускают плоской реализации.
Доказательство. Предположим, что граф К3.3 имеет плоскую реализацию. Тогда для него 
К3.3: К5:
Рис. 5.11 Рис. 5.12
В графе К3.3 нет циклов длины 3, так как любое ребро ведёт из одной группы вершин к другой, т.е. любой цикл в 
имеет длину ³4. Так как 
то для числа рёбер графа имеем
,
где 
– число рёбер, ограничивающих грань с номером 
, 
Полученное противоречие доказывает первую часть теоремы.
Допустим, что граф К 5 допускает плоскую реализацию. Для него 
Пусть 
имеют тот же смысл, что и раньше. Очевидно, 
Противоречие. <
Доказанная теорема допускает обращение.
ТЕОРЕМА Понтрягина – Куратовского. Для того, чтобы граф был планарным 
, чтобы он не содержал подграфов, гомеоморфных К3.3 и К5.<
Упражнения
1. Является ли планарным двудольный граф с двумя вершинами? Полный граф К6?
2. Является ли планарным граф
G 1: 12 13 14 25 26 27 35 37 36 46 47 45 56 67;
G 2: 12 23 34 48 81 14 82 45 56 67 87 46;
G 3: 12 13 15 18 23 24 34 38 45 46 47 56 57 58 67 78?
