Дискретная математика

159 одновременно либо внутри, либо вне шестиугольника и поэтому они обязательно пересекаются. Теорема доказана. Ясно, что каждый граф, содержащий К} и Кхз, не является планарным. Оказывается, что К; и К3 3 - по существу единственные непланарные графы в том смысле, что любой непланарный граф «содержит» один из них. Чтобы сформулировать это утверждение более точно, нам понадобится понятие гомеоморфных графов. Л Два графа гомеоморфны, если они оба могут быть получены из одного и того же графа включением в его ребра новых вершин степени 2. Графы, приведенные на рис. 5.32, Рис.5.32 гомеоморфны. Теорема 5.23 (теорема Куратовского - Понтрягина). Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного К$ или Доказательство. Необходимость. Графы К; и К^з непланарные, поэтому если граф содержит подграф, гомеоморфный любому из них, он хакже непланарен, Достаточность примем без доказательства. Операция включения в ребра графа новых вершин со степенями 2 называется расширением графа. Определим операцию стягивания графа. Пусть X = fv, и) ребро графа G, не являющееся петлёй. Элементарным стягиванием называется такая процедура: удаляем ребро х, отождествляя вершину V с вершиной и, отбрасываем все петли графа и отождествляем кратные рёбра. В результате получим некоторый граф G*, который считаем полученным элементарным стягиванием ребра х = (v,u). На рис. 5.33 приведены графы Gj и Gj, а также графы G] И , полученные операцией элементарного стягивания из G/ и G2 соответственно. Граф G называется стягиваемым к графу Н, если Н можно получить из G с помощью некоторой последовательности элементарных стягиваний. Примем без доказательства следующую теорему. Теорема 5.24 (Вагнер, Харари, Татт). Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых к или к Толщиной графа G называется наименьшее число планарных графов, объединение которых даёт О.