Fáry-tétel
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 

A Fáry-tétel igazolható teljes indukcióval. 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 
.
.
.
.
.
.
.
.
.
 .
.
.
.

Síkgráfok
Gráfelméleti tételek
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 A Fáry-tétel igazolható teljes indukcióval . 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 legfeljebblehet 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 legfeljebbszomszé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 mindenszorosan ö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 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 mindenszorosan ö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 jelenlegmegoldatlan . 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 aregulá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 . . . . . . . . . \ . . . . Síkgráfok Gráfelméleti tételek