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

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₄.

Теорема Вагнера є важливою попередницею теорії мінорів графа, яка досягла апогею з доведенням двох глибоких результатів із широкими наслідками — структурної теореми графів (узагальнення розкладу Вагнера на клікові суми графів, що не містять 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.