A Wagner-tétel a Pontrjagin-Kuratovszkij-tételhez szorosan kapcsolódó síkgráfok jellemzése .
Klaus Wagnerről kapta a nevét . A tétel kimondja, hogy egy véges gráf akkor és csak akkor sík, ha mellékei nem tartalmaznak sem K 5 -öt ( öt csúcsú teljes gráf ), sem K 3,3 -at ( közös gráf , teljes kétrészes gráf három csúcsgal minden részében). A tétel a gráf-mollok elméletének egyik legkorábbi munkája volt, és a Robertson-Seymour-tétel előfutáraként tekinthető .
Egy adott gráf síkbeli beágyazása egy gráf vizualizálása az euklideszi síkon , amelyet pontok csúcsként , görbék élként ábrázolnak, míg az éleknek csak az élek végén (a gráf csúcsain) lehetnek közös pontok. Egy adott gráf mollja egy másik gráf, amelyet csúcsok eltávolításával, élek eltávolításával és összehúzásával kapunk. Amikor egy él összehúzódik, végei egy csúcsba egyesülnek. A gráf-moll elmélet egyes változataiban az élek összehúzódása után kapott gráfot a hurkok és a többszörös élek eltávolításával egyszerűsítik, míg más változatokban a multigráfok megengedettek, de ezek a variációk nem elengedhetetlenek a Wagner-tételhez. Wagner tétele kimondja, hogy minden gráfnak vagy síkbeli beágyazása van, vagy két típus egyikének mollját tartalmazza - egy teljes gráfot K 5 vagy egy teljes kétrészes gráfot K 3,3 (egy gráfnak mindkét típusú mollja lehet).
Ha az adott gráf sík, akkor az összes minora is az – egy csúcs vagy egy él törlése nyilvánvalóan nem sérti a síkságot, és az él összehúzása is végrehajtható a síkság megőrzése mellett, ha az összehúzandó él egyik csúcsa helyén marad, és a második csúcsra eső összes él az összehúzott él mentén van. A moll-minimális nem sík gráf egy nem sík gráf, de minden megfelelő mollja (legalább egy él eltávolításával vagy összehúzásával kapott minor) síkbeli. A Wagner-tétel másik megfogalmazása szerint csak két kisebb-minimális nem síkbeli gráf létezik, ezek K 5 és K 3,3 .
Egy másik eredmény, amelyet néha Wagner-tételnek is neveznek, kimondja, hogy egy 4-es csúcshoz kapcsolódó gráf akkor és csak akkor sík, ha nem tartalmaz K5 - öt mellékként. Vagyis magasabb szintű kapcsolódás feltételezése esetén a K 3,3 gráf irrelevánsnak bizonyul a leírás szempontjából, így csak egy tiltott moll, a K 5 marad meg . Ennek megfelelően a Kelmans–Seymour-sejtés kimondja, hogy egy csúcs-5-ös gráf akkor és csak akkor síkbeli, ha nem tartalmazza a K5- öt topológiai minorként .
Wagner mindkét tételét 1937-ben publikálta [1] , már Kuratowski 1930-as publikálása után [2] azt a tételt , amely szerint egy gráf akkor és csak akkor sík, ha nem tartalmazza részgráfként ugyanazon tiltott gráfok egyikének felosztását. K 5 és K 3 ,3 . Kuratowski tétele erősebb, mint Wagner tétele – egy felosztás átalakítható azonos típusú molllá, ha az egyes leskálázási utak egy kivételével az összes élt összehúzzuk, de a mollról egy azonos típusú felosztásra való átalakítás nem mindig lehetséges. Két K 5 és K 3,3 gráf esetén azonban közvetlenül igazolható, hogy ezekből a gráfokból felosztással előállítható egy gráf, amely ezen gráfok közül legalább az egyiket mellékesen tartalmazza, így a két tétel ekvivalens [ 3] .
A Wagner-tétel négy összekapcsolt gráfokra vonatkozó változatának egyik következménye a K 5 -öt nem tartalmazó gráfok leírása . A tétel átfogalmazható úgy, hogy minden ilyen gráf vagy sík, vagy egyszerűbb részekre bontható. Ezzel az ötlettel azokat a gráfokat, amelyek nem tartalmaznak K5 - öt mellékként, egy síkgráf és egy hat csúcsú Wagner-gráf kombinációiból alkotott gráfokként írhatjuk le, amelyeket klikkösszegekkel ragasztottak össze . Például K 3,3 ily módon előállítható három síkgráf klikkösszegeivel, amelyek mindegyike a K 4 tetraéder gráf másolata .
Wagner tétele fontos előfutára a gráfmollok elméletének, amely két mélyreható eredmény bizonyításával érte el csúcspontját, amelyek széles következményekkel jártak: a strukturális gráftétel (a Wagner-féle felosztás általánosítása olyan gráfok klikkösszegeire, amelyek nem tartalmaznak K5 - öt mollként) [ 4] és a Robertson-Seymour-tétel (a gráfok tiltott kiskorúakat használó leírásának általánosítása, amely kimondja, hogy a kiskorú elvételének műveletével lezárt gráfcsaládokat véges számú tiltott kiskorú írja le) [5] . A Wagner-tétel analógiája kiterjeszthető a matroid elméletre . Különösen ugyanaz a K 5 és K 3,3 (három másikkal együtt) szerepel a grafikus matroidok leírásában , mint tiltott matroid minorok [6] .