Teorema Wagner este o caracterizare a grafurilor plane strâns legate de teorema Pontryagin-Kuratovsky .
Numit după Klaus Wagner . Teorema afirmă că un graf finit este plan dacă și numai dacă minorele sale nu includ nici K 5 ( un graf complet cu cinci vârfuri ) și nici K 3,3 ( un graf comun , un graf complet bipartit cu trei vârfuri în fiecare parte). Teorema a fost una dintre cele mai timpurii lucrări din teoria grafurilor minore și poate fi văzută ca un precursor al teoremei Robertson-Seymour .
O încorporare plană a unui grafic dat este o vizualizare a unui grafic pe planul euclidian , reprezentat prin puncte ca vârfuri și curbe ca muchii, în timp ce muchiile pot avea doar puncte comune la capetele muchiilor (la vârfurile graficului). Minorul unui graf dat este un alt graf obținut prin eliminarea vârfurilor, îndepărtarea și contractarea muchiilor. Când o muchie se contractă, capetele ei se îmbină într-un singur vârf. În unele versiuni ale teoriei grafurilor minore, graficul obținut după contracția muchiilor este simplificat prin eliminarea buclelor și a muchiilor multiple, în timp ce în alte versiuni sunt permise multigrafele , dar aceste variații nu sunt esențiale pentru teorema lui Wagner. Teorema lui Wagner afirmă că orice graf fie are o încorporare plană, fie conține un minor de unul dintre cele două tipuri - un graf complet K 5 sau un graf complet bipartit K 3,3 (un graf poate avea ambele tipuri de minore).
Dacă graficul dat este plan, atunci la fel sunt toate minorele sale - ștergerea unui vârf sau a unei muchii, evident, nu încalcă planaritatea, iar contracția unei muchii se poate face, de asemenea, păstrând planaritatea, dacă unul dintre vârfurile muchiei contractate este lăsat pe loc, iar toate muchiile incidente celui de-al doilea vârf sunt de-a lungul muchiei contractate. Un graf neplan minor-minim este un graf neplan, dar toate minorele sale proprii (minore obținute prin îndepărtarea sau contractarea a cel puțin o muchie) sunt plane. O altă formulare a teoremei lui Wagner este că există doar două grafice neplanare minore-minimale, acestea sunt K 5 și K 3,3 .
Un alt rezultat, uneori numit și teorema lui Wagner, afirmă că un graf cu 4 vârfuri este planar dacă și numai dacă nu conține K 5 ca minor. Adică, în ipoteza unui nivel mai ridicat de conectivitate, graficul K 3,3 se dovedește a fi irelevant pentru descriere, astfel încât rămâne doar un minor interzis, K 5 . În consecință, conjectura Kelmans–Seymour afirmă că un graf legat de vârfuri 5 este plan dacă și numai dacă nu conține K 5 ca minor topologic .
Wagner a publicat ambele teoreme în 1937 [1] , deja după publicarea lui Kuratowski în 1930 [2] a teoremei , conform căreia un graf este plan dacă și numai dacă nu conține ca subgraf o subdiviziune a unuia dintre aceleași grafuri interzise. K5 şi K3,3 . _ _ Teorema lui Kuratowski este mai puternică decât teorema lui Wagner - o subdiviziune poate fi convertită într-o subdiviziune minoră de același tip prin contractarea tuturor muchiilor, cu excepția uneia, în fiecare cale de reducere a scalei, dar conversia dintr-o subdiviziune minoră într-o subdiviziune de același tip nu este întotdeauna posibilă. Totuși, în cazul a două grafice K 5 și K 3,3 , se poate dovedi direct că un grafic care conține cel puțin unul dintre aceste grafice ca minor poate fi obținut din aceste grafice prin subdiviziune, deci cele două teoreme sunt echivalente [ 3] .
Una dintre consecințele versiunii teoremei lui Wagner pentru grafuri cu patru conexiuni este descrierea grafurilor care nu conțin K 5 ca minor. Teorema poate fi reformulată ca afirmând că orice astfel de grafic este fie plan, fie poate fi descompus în părți mai simple. Folosind această idee, graficele care nu conțin K 5 ca minor pot fi descrise ca grafice formate din combinații ale unui graf planar și a unui graf Wagner cu șase vârfuri lipite împreună prin sume de clică . De exemplu, K 3,3 poate fi generat în acest fel prin sume de clicuri a trei grafice plane, fiecare dintre acestea fiind o copie a graficului tetraedric K 4 .
Teorema lui Wagner este un precursor important al teoriei grafurilor minore, care a atins apogeul prin demonstrarea a două rezultate profunde cu consecințe largi - teorema grafului structural (o generalizare a descompunerii lui Wagner în sume clică de grafuri care nu conțin K 5 ca minor) [ 4] și teorema Robertson-Seymour (o generalizare a descrierii graficelor folosind minori interziși, afirmând că orice familie de grafice închise prin operațiunea de a lua un minor este descrisă de un număr finit de minori interziși) [5] . Analogia teoremei lui Wagner poate fi extinsă la teoria matroidei . În special, aceleași K 5 și K 3,3 (împreună cu alte trei) apar în descrierea matroizilor grafici ca minori matroizi interziși [6] .