Введение

В теории графов теорема Вагнера — это математическая характеристика планарных графов через запрещенные миноры, названная в честь Клауса Вагнера. Она утверждает, что конечный граф является планарным тогда и только тогда, когда он не содержит в качестве минора ни K5 (полный граф на пяти вершинах), ни K3,3 (граф полезности, полный двудольный граф на шести вершинах). Это был один из первых результатов в теории миноров графов и может рассматриваться как предшественник теоремы Робертсона — Сеймура.

Определения и формулировка

Плоское встраивание данного графа — это чертёж графа в евклидовой плоскости, где вершины представлены точками, а рёбра — кривыми, таким образом, чтобы единственными точками пересечения рёбер были общие конечные точки. Минор данного графа — это другой граф, полученный удалением вершин, удалением рёбер и стягиванием рёбер. При стягивании ребра его две конечные точки объединяются в одну вершину. В некоторых версиях теории миноров графа граф, полученный в результате стягивания, упрощается удалением петель и кратных рёбер, в то время как в других версиях допускаются мультиграфы, но это не влияет на теорему Вагнера. Теорема Вагнера утверждает, что каждый граф либо имеет плоское встраивание, либо содержит минор одного из двух типов: полный граф K5 или полный двудольный граф K3,3. (Возможно, один и тот же граф содержит оба типа миноров.) Если данный граф плоский, то все его миноры также плоские: удаление вершин и рёбер очевидно сохраняет планарность, а стягивание рёбер также может быть выполнено с сохранением планарности, оставляя одну из двух конечных точек стягиваемого ребра на месте и проводя все рёбра, инцидентные другой конечной точке, по пути стягиваемого ребра. Минимальный непланарный граф — это граф, который не является планарным, но все его собственные миноры (миноры, полученные удалением или стягиванием хотя бы одного ребра) планарны. Другая формулировка теоремы Вагнера заключается в том, что существует только два минимальных непланарных графа: K5 и K3,3. Другой результат, также иногда называемый теоремой Вагнера, утверждает, что 4-связный граф планарен тогда и только тогда, когда он не содержит минор K5. То есть, при условии более высокой связности граф K3,3 становится ненужным в характеристике, остаётся только один запрещённый минор — K5. Соответственно, гипотеза Келманса — Сеймура утверждает, что 5-связный граф планарен тогда и только тогда, когда он не содержит K5 в качестве топологического минора.

История и отношение к теореме Куратовского

Вагнер опубликовал обе теоремы в 1937 году, после публикации теоремы Куратовского в 1930 году, которая утверждает, что граф планарный тогда и только тогда, когда он не содержит в качестве подграфа деление одного из тех же двух запрещенных графов K5 и K3,3. В определенном смысле теорема Куратовского сильнее теоремы Вагнера: деление можно преобразовать в минор того же типа, стянув все, кроме одного ребра, в каждом пути, образованном процессом деления, но преобразовать минор в деление того же типа не всегда возможно. Однако для графов K5 и K3,3 легко доказать, что если граф имеет хотя бы один из этих двух графов в качестве минора, то он также имеет хотя бы один из них в качестве деления, поэтому обе теоремы эквивалентны.

Последствия

Одним из следствий более сильной версии теоремы Вагнера для четырех связных графов является характеристизация графов, не содержащих минор K5. Теорему можно перефразировать, утверждая, что любой такой граф либо планарный, либо может быть разложен на более простые части. Используя эту идею, графы, не содержащие минор K5, можно охарактеризовать как графы, которые могут быть образованы комбинациями планарных графов и графа Вагнера с восемью вершинами, склеенными операциями суммирования клик. Например, K3,3 можно образовать таким образом как сумму клик из трех планарных графов, каждый из которых является копией тетраэдрического графа K4. Теорема Вагнера является важным предшественником теории миноров графов, которая привела к доказательствам двух глубоких и значимых результатов: теоремы о структуре графов (обобщение разложения на сумму клик Вагнера для графов, не содержащих минор K5) и теоремы Робертсона — Сеймура (обобщение запрещенной характеристики миноров для планарных графов, утверждающей, что любое семейство графов, замкнутое относительно операции взятия миноров, характеризуется конечным числом запрещенных миноров). Аналоги теоремы Вагнера также можно распространить на теорию матроидов: в частности, те же два графа K5 и K3,3 (наряду с тремя другими запрещенными конфигурациями) появляются в характеристике графических матроидов запрещенными минорами матроидов.