Жемчужина Эйлера

У этой формулы есть интересное следствие: в любом представлении планарного графа с E ребрами и V вершинами количество граней одинаково. Иными словами, если десять человек нарисуют планарный граф, поставив точки там, где пожелают, и проведя ребра, так чтобы они не пересекались, то у всех графов будет одно и то же число граней (F = 1 + E — V, если не считать неограниченной грани). Например, на рис. 13.5 показан граф с четырьмя вершинами и шестью ребрами и два его планарных представления с тремя гранями каждое.

Рис. 13.5. Два разных планарных представления одного графа будут иметь одно и то же число граней

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

В полном графе с n вершинами, обозначаемом K_n, n вершин, и каждая пара вершин соединена ровно одним ребром. Это самый большой возможный граф с n вершинами, не имеющий ни петель, ни параллельных ребер. Графы K₁… K₅ показаны на рис. 13.6. Удалив петли из графа домино (рис. 11.11), мы получили бы граф K₇.

Рис. 13.6. Полные графы K₁, K₂, K₃, K₄ и K₅

С полным графом тесно связан полный двудольный граф. Он обладает тем свойством, что множество вершин можно разделить на два подмножества U и V, так что никакие две вершины, принадлежащие U, и никакие две вершины, принадлежащие V, не соединены ребром, а каждая вершина из U соединена с каждой вершиной из V ровно одним ребром. Если U содержит m вершин, а V— n вершин, то соответствующий полный двудольный граф обозначается K_m,n. Графы K_3,2 и K_3,3 показаны на рис. 13.7. Типичный пример полного двудольного графа, который приводится в любом начальном учебнике по теории графов, — граф ресурсоснабжающих компаний. Множество U состоит из компаний (газовой, водопроводной, электрической и т. д.), а множество V — из клиентов. Поскольку каждый клиент должен получать ресурсы каждого вида, то получающийся граф полный двудольный.

Рис. 13.7. Полные двудольные графы K_3,2 и K_3,3

Мы хотели бы знать, какие из полных и полных двудольных графов планарные. Легко показать, что графы K₁, K₂, K₃, K₄, K_m,1 и K_m,2 планарные. Например, на рис. 13.8 мы видим, что K₄ и K_3,2 планарные. Оказывается, что все остальные графы интересующего нас вида непланарные. Воспользуемся формулой Эйлера, чтобы доказать, что K₅ и K_3,3 непланарные.

Рис. 13.8. K₄ и K_3,2 — планарные графы

Чтобы доказать, что K₅ непланарный, мы воспользуемся техникой доказательства от противного. Предположим, что утверждение, которое мы хотим доказать, неверно (т. е. что граф K₅ планарный), и покажем, что это приводит к логическому противоречию. Тогда можно будет заключить, что K₅ непланарный. Г. Х. Харди писал: «Метод доказательства reductio ad absurdum, столь любимый Евклидом, — один из самых лучших инструментов математика. Это гораздо более “хитроумный” гамбит, чем любой шахматный гамбит: шахматист может пожертвовать пешку или даже фигуру, но математик жертвует партию»¹⁰⁴.

Предположим, что K₅ — планарный граф. Тогда мы сможем нарисовать K₅ на плоскости, так что никакие два ребра не будут пересекаться. K₅ имеет 5 вершин и 10 ребер. Формула Эйлера для планарных графов утверждает, что V — E + F = 2, поэтому в нашем планарном чертеже K₅ должно быть 7 граней, включая неограниченную (потому что 2 = F — 10 + 5).

Каждое ребро является общей границей двух граней, поэтому 2E = pF, где p — среднее число сторон по всем граням. K₅ — полный граф, поэтому в нем нет ни петель, ни параллельных ребер. Так как нет петель, то не существует граней, ограниченных только одним ребром, а поскольку нет параллельных ребер, то не существует граней, ограниченных двумя ребрами. Следовательно, среднее число ребер на одну грань должно быть не меньше трех. Это значит, что p ≥ 3 и 2E ≥ 3F. Но из того, что F = 7 и E = 10, следует, что 20 ≥ 21, т. е. мы пришли к противоречию. Поэтому K₅ должен быть непланарным.

Аналогично можно доказать, что полный двудольный граф K_3,3 непланарный (попробуйте сами!). Главное отличие заключается в том, что, поскольку K_3,3 двудольный, путь, который начинается и заканчивается в одной и той же вершине, должен иметь четное число ребер. Поэтому в нем не может быть также граней с тремя сторонами.

В общем случае справедлива следующая теорема.

Граф K_n не является планарным для n ≥ 5, а граф K_{m n} не является планарным, когда одновременно m ≥ 3 и n ≥ 3.

Оказывается, что в некотором смысле K₅ и K_3,3 — единственные препятствия, мешающие графу быть планарным. Знаменитая теорема Куратовского-Понтрягина утверждает, что граф может быть непланарным, только если он содержит в качестве подграфа K₅ или K_3,3. Например, граф на рис. 13.9 непланарный, потому что содержит копию K₅.

Рис. 13.9. Пример непланарного графа, содержащего K₅