Теорема Вагнера

Теорема Вагнера — характеризация планарных графов тесно связанная с теоремой Понтрягина — Куратовского.

K₅ (слева) и K_3,3 (справа) в качестве миноров непланарного графа Петерсена (маленькие цветные кружочки и чёрные рёбра). Миноры можно сформировать путём удаления красной вершины и стягивания рёбер в жёлтые круги

Кликовая сумма двух планарных графов и графа Вагнера, образующая граф без K₅

Названа в честь Клауса Вагнера. Теорема утверждает, что конечный граф является планарным тогда и только тогда, когда его миноры не включают ни K₅ (полный граф с пятью вершинами), ни K_3,3 (коммунальный граф, полный двудольный граф с тремя вершинами в каждой доле). Теорема была одной из наиболее ранних работ в теории миноров графа и её можно рассматривать как предшественницу теоремы Робертсона — Сеймура.

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

Планарное вложение заданного графа — это визуализация графа на евклидовой плоскости, представленная точками в качестве вершин и кривыми в качестве рёбер, при этом рёбра могут иметь общие точки только в концах рёбер (в вершинах графа). Минор заданного графа — это другой граф, полученный путём удаления вершин, удалением и стягиванием рёбер. Когда ребро стягивается, его концы сливаются в одну вершину. В некоторых версиях теории миноров графа полученный после стягивания рёбер граф упрощается путём удаления петель и кратных рёбер, в то время как в других версиях мультиграфы разрешаются, но эти вариации несущественны для теоремы Вагнера. Теорема Вагнера утверждает, что любой граф либо имеет планарное вложение, либо содержит минор одного из двух типов — полный граф K₅ или полный двудольный граф K_3,3 (граф может иметь оба типа миноров).

Если данный граф планарен, то таковы и все его миноры — удаление вершины или ребра очевидно не нарушает планарности, а стягивание ребра также можно сделать с сохранением планарности, если одну из вершин стягиваемого ребра оставить на месте, а все рёбра, инцидентные второй вершине, пустить вдоль стягиваемого ребра. Минорно минимальный непланарный граф — это непланарный граф, но все его собственные миноры (миноры, полученные по меньшей мере удалением или стягиванием одного ребра) планарны. Другая формулировка теоремы Вагнера — есть только два минорно минимальных непланарных графа, это K₅ и K_3,3.

Другой результат, который иногда также называют теоремой Вагнера, утверждает, что вершинно 4-связный граф планарен тогда и только тогда, когда он не содержит K₅ в качестве минора. То есть при предположении более высокого уровня связности граф K_3,3 оказывается несущественным для описания, так что остаётся только один запрещённый минор, K₅. Соответственно, гипотеза Келманса – Сеймура утверждает, что вершинно 5-связный граф планарен тогда и только тогда, когда не содержит K₅ в качестве топологического минора.

История и связь с теоремой Понтрягина — Куратовского

Вагнер опубликовал обе теоремы в 1937, уже после публикации Куратовского в 1930 теоремы, согласно которой граф планарен тогда и только тогда, когда он не содержит в качестве подграфа подразделение одного из тех же самых запрещённых графов K₅ и K_3,3. Теорема Куратовского сильнее теоремы Вагнера — подразделение может быть преобразовано в минор того же типа путём стягивания всех, кроме одного, рёбер в каждом пути, полученном при разукрупнении, а вот преобразование из минора в подразделение того же типа не всегда возможно. Однако в случае двух графов K₅ и K_3,3 можно доказать напрямую, что граф, содержащий по меньшей мере один из этих графов в качестве минора, может быть получен из этих графов путём подразделения, так что две теоремы эквивалентны.

Следствия

Одним из следствий версии теоремы Вагнера для четырёхсвязных графов является описание графов, не содержащих K₅ в качестве минора. Теорему можно перефразировать как утверждение, что любой такой граф либо планарен, или может быть разложен на более простые части. Если использовать эту идею, графы, не содержащие K₅ в качестве минора, можно описать как графы, образованные комбинациями планарного графа и графа Вагнера с шестью вершинами, склеенные вместе посредством сумм по клике. Например, K_3,3 можно образовать этим способом посредством сумм по клике из трёх планарных графов, каждый из которых является копией тетраэдрального графа K₄.

Теорема Вагнера является важной предшественницей теории миноров графа, которая достигла апогея доказательством двух глубоких результатов с широкими следствиями — cтруктурной теоремы графов (обобщение разложения Вагнера на кликовые суммы графов, не содержащих K₅ в качестве минора) и теоремы Робертсона — Сеймура (обобщение описания графов с помощью запрещённых миноров, утверждающая, что любое семейство графов, замкнутое по операции взятия минора описывается конечным числом запрещённых миноров) . Аналогия теоремы Вагнера может быть распространена на теорию матроидов. В частности, те же самые K₅ и K_3,3 (вместе с тремя другими) появляются в описании графовых матроидов запрещёнными матроидными минорами.

Литература

• K. Wagner. Über eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. — 1937. — Т. 114. — С. 570–590. — doi:10.1007/BF01594196.
• Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie (фр.) // Fund. Math.. — 1930. — Т. 15. — С. 271–283.
• J. A. Bondy, U.S.R. Murty. Graph Theory. — Springer, 2008. — Т. 244. — С. 269. — (Graduate Texts in Mathematics). — ISBN 9781846289699.
• László Lovász. Graph minor theory. — 2006. — Т. 43, вып. 1. — С. 75–86. — doi:10.1090/S0273-0979-05-01088-8.
• Gary Chartrand, Linda Lesniak, Ping Zhang. Graphs & Digraphs. — 5th. — CRC Press, 2010. — С. 307. — ISBN 9781439826270.
• P. D. Seymour. On Tutte's characterization of graphic matroids // Annals of Discrete Mathematics. — 1980. — Т. 8. — С. 83–90. — doi:10.1016/S0167-5060(08)70855-0.