Wagnerin lause on Pontryagin - Kuratovsky -lauseeseen läheisesti liittyvien tasograafien karakterisointi .
Nimetty Klaus Wagnerin mukaan . Lauseen mukaan äärellinen graafi on tasomainen silloin ja vain, jos sen sivumerkit eivät sisällä K 5 :tä ( täydellinen graafi , jossa on viisi kärkeä ) eikä K 3,3 :a ( yhteisögraafi , täydellinen kaksiosainen graafi , jossa on kolme kärkeä kussakin osassa). Lause oli yksi varhaisimmista teoksista graafimoorillien teoriassa, ja sitä voidaan pitää Robertson-Seymourin lauseen edeltäjänä .
Tietyn graafin tasomainen upottaminen on graafin visualisointi euklidisella tasolla , jota edustavat pisteet kärkipisteinä ja käyrät reunoina, kun taas reunoilla voi olla yhteisiä pisteitä vain reunojen päissä (graafin pisteissä). Tietyn graafin molli on toinen graafi, joka saadaan poistamalla kärkipisteitä, poistamalla ja supistamalla reunoja. Kun reuna supistuu, sen päät sulautuvat yhdeksi kärjeksi. Joissakin graafisen molliteorian versioissa reunojen kutistumisen jälkeen saatua graafia yksinkertaistetaan poistamalla silmukat ja useat reunat, kun taas toisissa versioissa multigrafit ovat sallittuja, mutta nämä variaatiot eivät ole välttämättömiä Wagnerin lauseen kannalta. Wagnerin lause sanoo, että missä tahansa graafissa on joko tasomainen upotus tai se sisältää mollin jommankumman kahdesta tyypistä - täydellisen graafin K 5 tai täydellisen kaksiosaisen graafin K 3,3 (graafissa voi olla molempia mollityyppejä).
Jos annettu graafi on tasomainen, niin ovat myös kaikki sen alamerkit - kärjen tai reunan poistaminen ei tietenkään loukkaa tasomaisuutta, ja reunan supistus voidaan tehdä myös tasomaisuutta säilyttäen, jos yksi supistettavan reunan kärjeistä on jätetään paikoilleen, ja kaikki toiseen kärkeen tulevat reunat ovat supistuvaa reunaa pitkin. Minimi-minimaali epätasograafi on ei-tasograafi, mutta kaikki sen varsinaiset minorit (vähintään yhden reunan poistamalla tai supistamalla saadut alamerkit) ovat tasomaisia. Toinen Wagnerin lauseen muotoilu on, että on vain kaksi pienempää-minimaalista ei-tasograafista kuvaajaa, nämä ovat K 5 ja K 3,3 .
Toinen tulos, jota joskus kutsutaan myös Wagnerin lauseeksi, väittää, että kärkeen 4 yhdistetty graafi on tasomainen silloin ja vain, jos se ei sisällä K 5 :tä mollina. Toisin sanoen, jos oletetaan, että liitettävyys on korkeampi, graafi K 3,3 osoittautuu kuvauksen kannalta merkityksettömäksi, joten jäljelle jää vain yksi kielletty molli, K 5 . Vastaavasti Kelmans–Seymour-oletus väittää, että kärkipisteeseen 5 yhdistetty graafi on tasomainen silloin ja vain, jos se ei sisällä K5 :tä topologisena sivuarvona .
Wagner julkaisi molemmat lauseet vuonna 1937 [1] , jo Kuratowskin vuonna 1930 [2] julkaisemisen jälkeen lauseen , jonka mukaan graafi on tasomainen silloin ja vain, jos se ei sisällä alagraafina saman kielletyn graafin alajakoa. K 5 ja K 3, 3 . Kuratowskin lause on vahvempi kuin Wagnerin lause - alajako voidaan muuntaa samantyyppiseksi molliksi supistamalla jokaisen alasskaalauspolun kaikki reunat yhtä lukuun ottamatta, mutta muuntaminen mollista samantyyppiseksi alajaoksi ei ole aina mahdollista. Kahden graafin K 5 ja K 3,3 tapauksessa voidaan kuitenkin osoittaa suoraan, että näistä graafista voidaan saada alajaolla graafi, joka sisältää vähintään yhden näistä graafisista sivuista, joten nämä kaksi lausetta ovat ekvivalentteja [ 3] .
Yksi seurauksista Wagnerin lauseen versiosta neliliitetyille graafeille on sellaisten graafien kuvaus, jotka eivät sisällä K5 : tä sivuaineena. Lause voidaan muotoilla uudelleen niin, että mikä tahansa tällainen graafi on joko tasomainen tai se voidaan jakaa yksinkertaisempiin osiin. Tämän idean avulla graafit, jotka eivät sisällä K 5 :tä sivuaineena, voidaan kuvata graafisiksi, jotka muodostuvat tasograafin ja kuuden kärjen Wagner-graafin yhdistelmistä, jotka on liimattu yhteen klikkisummilla . Esimerkiksi K 3,3 voidaan muodostaa tällä tavalla kolmen tasograafin klikkisummalla, joista jokainen on kopio tetraedrisesta graafista K 4 .
Wagnerin teoreema on tärkeä edeltäjä graafimoorillien teorialle, joka saavutti huippunsa osoittamalla kaksi syvällistä tulosta, joilla on laajat seuraukset — rakennegraafilause (yleistys Wagnerin hajoamisesta graafien klikkisummuiksi, jotka eivät sisällä K5 :tä mollina ) [ 4] ja Robertson-Seymour-lause (yleistys graafien kuvauksesta, jossa käytetään kiellettyjä alaikäisiä, jossa todetaan, että mitä tahansa alaikäisen ottamisen sulkemaa graafiperhettä kuvaa rajallinen määrä kiellettyjä alaikäisiä) [5] . Wagnerin lauseen analogia voidaan laajentaa matroiditeoriaan . Erityisesti samat K 5 ja K 3,3 (yhdessä kolmen muun kanssa) esiintyvät graafisten matroidien kuvauksessa kiellettyinä matroid-molleina [6] .