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

Теорема Вагнера — характеризація планарних графів, тісно пов'язана з теоремою Понтрягіна — Куратовського.

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

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

Названа на честь ^[ru]. Теорема стверджує, що скінченний граф є планарним тоді й лише тоді, коли серед його мінорів немає ні K₅ (повний граф із п'ятьма вершинами), ні K_3,3 (комунальний граф, повний двочастковий граф із трьома вершинами в кожній частці). Теорема є однією з найраніших робіт у теорії мінорів графа і її можна розглядати як попередницю теореми Робертсона — Сеймура.

Визначення та формулювання теореми

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

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

Інший результат, який іноді також називають теоремою Вагнера, стверджує, що 4-вершинно-зв'язний граф планарний тоді й лише тоді, коли він не містить K₅ як мінор. Тобто, за припущення вищого рівня зв'язності граф K_3,3 виявляється несуттєвим для опису, так що залишається тільки один заборонений мінор, K₅. Відповідно, ^[en] стверджує, що 5-вершинно-зв'язний граф планарний тоді й лише тоді, коли не містить K₅ як топологічний мінор.

Історія і зв'язок з теоремою Понтрягіна — Куратовського

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

Наслідки

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

Теорема Вагнера є важливою попередницею теорії мінорів графа, яка досягла апогею з доведенням двох глибоких результатів із широкими наслідками — структурної теореми графів (узагальнення розкладу Вагнера на клікові суми графів, що не містять K₅ як мінор) і теореми Робертсона — Сеймура (узагальнення опису графів за допомогою заборонених мінорів, яка стверджує, що будь-яке сімейство графів, замкнуте за операцією взяття мінора, описується скінченним числом заборонених мінорів). Аналогію теореми Вагнера можна поширити на теорію матроїдів. Зокрема, ті ж самі K₅ і K_3,3 (разом з трьома іншими) з'являються в описі ^[en] забороненими ^[en].

Примітки

1. Wagner, 1937, с. 570–590.
2. Kuratowski, 1930, с. 271–283.
3. Bondy, Murty, 2008, с. 269.
4. Lovász, 2006, с. 75–86.
5. Chartrand, Lesniak, Zhang, 2010, с. 307.
6. Seymour, 1980, с. 83–90.

Література

• 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) — .
• 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. — .
• 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.