A matematika, azon belül a gráfelmélet területén a Fáry-tétel vagy Fáry–Wagner-tétel kimondja, hogy bármely egyszerű síkbarajzolható gráf beágyazható a síkba úgy is, hogy a gráf éleit egyenes szakaszok alkotják. Más szóval, ha megengedjük, hogy a gráf éleit egyenes szakaszok helyett görbék jelöljék, az nem teszi lehetővé több gráf lerajzolását. A tételt Fáry Istvánról nevezték el, bár egymástól függetlenül , és is igazolták.
Bizonyítás thumb|right|A Fáry-tétel bizonyításának egy indukciós lépése. A Fáry-tétel igazolható teljes indukcióval.Ez a bizonyítás megtalálható: . Vegyünk egy csúccsal rendelkező egyszerű síkgráfot; ha szükséges, adjunk -hez éleket addig („háromszögeljük”), amíg maximális síkgráf nem lesz. Ekkor minden tartománya háromszög lesz, hiszen bármely háromnál több szögű tartományhoz a síkba rajzolhatóság fenntartásával hozzáadható egy új él, ami ellentmond a korábbi követelménynek, hogy maximális síkgráf. Válasszunk ki három csúcsot: , melyik a háromszögű tartományát alkotják. Teljes indukcióval bizonyítjuk, hogy -re létezik -nek olyan egyenes szakaszokból álló síkba rajzolása, melynél az háromszög a síkba ágyazás külső tartományával határos. Alapesetként induljunk ki a triviális esetből, ahol , és adják összes csúcsát. Máskülönben bármely -beli csúcsnak legalább három szomszédja lenne.
A síkgráfokra vonatkozó Euler-formula alapján éleinek száma ; ekvivalens módon, ha definiáljuk gráf csúcsának „hiányát” -nek, akkor a hiányok összege . minden csúcsának legfeljebb 3 lehet a hiánya, ezért legalább négy pozitív hiánnyal rendelkező csúcs van a gráfban. Válasszunk egy csúcsot, ami különbözik az , és csúcsoktól, és legfeljebb 5 szomszéddal rendelkezik. A gráfot szerkesszük meg úgy, hogy a csúcsot eltávolítjuk -ből, és az így kapott tartományt újraháromszögeljük. Az indukció alapján a -nek létezik egyenes szakaszokból álló síkba rajzolása, melynél az a külső tartománnyal határos. Eltávolítva a -hez hozzáadott éleket egy legfeljebb öt oldalú sokszög jön létre, amibe -t illesztve készül el a síkba rajzolás. Chvátal művészeti galéria tétele alapján létezik -nek olyan belső pontja, amibe -t elhelyezve a -nek a csúcsaihoz húzott élei nem metszik a többi élt, ezzel befejezve a bizonyítást.
A bizonyítás indukciós lépése a jobb oldali ábrán látható.
Kapcsolódó eredmények De Fraysseix, Pach és Pollack megmutatták, hogy lehetséges lineáris időben megtalálni egy a gráf méretével lineáris méretű (négyzetes méretű univerzális ponthalmazt alkotó) rácson a gráf egyenes szakaszos reprezentációját. Schnyder hasonló módszerrel igazolt javított korlátokat és karakterizációt a síkgráfokkal kapcsolatban, az incidencia-részbenrendezett halmaz alapján. Munkája arra volt kihegyezve, hogy létezik a maximális síkgráfok éleinek egy speciális, három fagráffá történő particionálása, amit Schnyder woodnak neveznek.
A Tutte-féle rugók tétele állítása szerint minden 3-szorosan összefüggő síkbarajzolható gráf lerajzolható a síkban oly módon, hogy élei egyenes szakaszok, és a külső tartomány konvex sokszög (Tutte 1963). A tétel nevének az az eredete, hogy az ilyen beágyazás a gráf éleibe helyezett rugórendszer egyensúlyi helyzetének ismeretében állítható elő.
A Steinitz-tétel kimondja, hogy minden 3-szorosan összefüggő síkbarajzolható gráf kifejezhető egy háromdimenziós térbeli konvex poliéder éleiként. Egy gráf a Tutte-féle rugók tételében leírt egyenes szakaszos síkba rajzolása megkapható a poliéder-megfeleltetés síkra vetítésével.
A körpakolási tétel szerint minden síkgráf reprezentálható a sík egymást nem metsző körei metszetgráfjaként. A gráf minden csúcsát a megfelelő kör középpontjába helyezve megkapható az egyenes szakaszokkal történő reprezentáció.
Heiko Harborth vetette fel, hogy vajon lerajzolható-e minden síkbarajzolható gráf egyenes szakaszokkal oly módon, hogy az élek hosszai egész számok legyenek.; ; ; . A Harborth-sejtés jelenleg (2016) megoldatlan. Egész hosszúságú szakaszokkal történő síkba ágyazások azonban egyes gráfosztályok esetében léteznek, ilyenek például a 3-reguláris gráfok..
felteszi a kérdést, hogy vajon minden láncmentesen beágyazható gráf esetén létezik-e a három dimenziós euklideszi térbe való olyan láncmentes beágyazás is, amiben az éleket egyenes szakaszok reprezentálják – ez a Fáry-tétel háromdimenziós analógiájának tekinthető.
Jegyzetek
Irodalom . . . . . . . . . . . . .
Kategória:Síkgráfok Kategória:Gráfelméleti tételek