Kuratowski-tétel
A Kuratowski-tétel a gráfelméletben egy gráf részgráfjainak tulajdonságai alapján fogalmaz meg szükséges és elégséges kritériumot arra, hogy a gráf síkbarajzolható legyen.
A tétel állítása szerkesztés
Kazimierz Kuratowski lengyel matematikus 1930-ban bizonyította az alábbi tételt[1]
Tétel – Kuratowski síkbarajzolhatósági tétele – Egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz felosztott K3,3-at vagy felosztott K5-öt.
Itt K3,3 a (3,3) párhoz tartozó teljes páros gráf (a három ház–három kút-gráf), K5 az öt csúcspontú teljes gráf (a „teljes ötös”).
Egy gráfról akkor mondjuk, hogy felosztott H, ha a gráf a H gráf éleinek pontokkal való felosztásával jön létre. Ezt úgy kell érteni, hogy egy élen beiktatunk 0 vagy több újabb csúcsot (például •——• élhez hozzáveszünk még két csúcsot: •—•—•—•).
Ugyanezen tétel ekvivalens módon átfogalmazott kritériuma, ha nem tartalmaz a K3,3-mal vagy K5-tel homeomorf részgráfot.
Például az ábrán látható gráf nem tartalmaz ugyan K5-öt és K3,3-at, de van olyan részgráfja, mely izomorf K3,3-mal, így biztosan nem síkbarajzolható. (Ha a kék utat úgy képzeljük, mint a K3,3 egy élének felosztását, akkor világos, hogy maga a gráf homeomorf K3,3-mal)
Bizonyítás szerkesztés
Szükséges fogalmak és tételek szerkesztés
A tétel igazolásához fel kell használnunk az Euler–Descartes-féle poliédertételt, azaz a nevezetes c + l = e + 2 azonosságot, ahol c a csúcsok száma, l a lapoké, és e az éleké. Ezen kívül szükségünk lesz az alábbi tételre:
Tétel – A G gráf 3-összefüggő akkor és csak akkor, ha előáll a teljes négyesből a következő műveletekkel:
- egy már létező élnek bevesszük egy párhuzamos példányát;
- vegyünk egy legalább negyedfokú z pontot; a z-be menő éleket osszuk két, legalább kételemű csoportra; a z pont helyett vegyünk egy éllel összekötött pontpárt, z1-et és z2-t; a z-be menő élek első csoportját helyettesítsük a z1-be menő élekkel, a második csoportját a z2-be menő élekkel.
Megjegyzés. A párhuzamos élek bevétele azért kell, mert különben nem minden egyszerű 3-összefüggő gráfot lehetne ezen a módon létrehozni.
Végül a következő lemmára:
Lemma – Ha egy gráfban nincs felosztott K5 és K3,3, akkor élösszehúzás után sem lesz benne.
Lényegi rész szerkesztés
Tétel – Tutte – Ha a G = (V,E) gráf 3-összefüggő, egyszerű, nem tartalmaz felosztott K3,3-at és K5-öt, akkor síkba ágyazható úgy, hogy minden élt egyenes szakasz jelöl, az éleknek csak a végpontja lehet közös, és az összes tartomány konvex (a külső tartomány kivételével).
Bizonyítás – Ha a gráfnak 4 pontja van, akkor a gráf a teljes négyes, ami síkba ágyazható a kívánt módon. Feltehetjük, hogy V mérete legalább 5.
A lemma miatt van x1 és x2, hogy az x1x2, élt összehúzva egy G1 összefüggő gráfot kapunk. Ez nem tartalmaz felosztott K3,3-at és K5-öt, ezért indukció miatt síkba rajzolható a kívánt módon.
Jelölje az összehúzott pontot x. G1 \ {x} 2-összefüggő, ezért G1 \ {x} minden tartományát a gráf egy köre határolja. Jelölje K azt a kört, amely x-et belsejében tartalmazza.
Állítás – x1 és x2 egyikének van olyan, a másiktól különböző szomszédja, amely nem szomszédja a másiknak.
Tegyük fel indirekt, hogy nem ez a helyzet. A 3-összefüggőség miatt van x1 és x2-nek három közös szomszédja: u,v,z. Ekkor az x1,x2,u,v,z pontok a K körrel együtt egy felosztott K5-öt adnak, ez ellentmondás.
Tehát az állítás szerint van például x1 -nek olyan szomszédja, ami nem szomszédos x2-vel. Nevezzük ezt a szomszédot u-nak. Innen elindulva K mentén mindkét irányban lesz egy első pont, ami szomszédjax2-nek. x2 legalább harmadfokú, ezért ez a két pont, s és t különböző.
Állítás – x1 minden szomszédja K-nak az st ívén van, mint u.
Különben, ha például a v pont a másik íven lenne, akkor x1,x2,u,v,s,t a K körrel együtt egy felosztott K3,3-at határozna meg.
Ezek szerint az x pont szétnyitható úgy, hogy a G gráfot a kívánt módon síkba ágyazzuk.
A bizonyítás befejezése szerkesztés
Tétel - Egy gráf síkbarajzolható akkor és csak akkor, ha nem tartalmaz felosztott K3,3-at és K5-öt.
Az Euler-formulával belátható, hogy K3,3 és K5 nem síkba rajzolható, mert a formulából sehogy sem jön ki az élek száma. Tehát ezek a gráfok nem síkba rajzolhatók, így az ilyeneket felosztva tartalmazó gráfok sem.
A másik irányt indirekt módon bizonyítjuk. Feltesszük, hogy van egy minimális ellenpélda, ami nem tartalmaz felosztott K3,3-at és K5-öt, mégsem rajzolható síkba. Belátjuk, hogy nincs ilyen ellenpélda.
Jelöljük ezt az ellenpéldát G-vel. Könnyen látható, hogy összefüggő és egyszerű.
Állítás - G 2-összefüggő. Ha t elvágó pont lenne, akkor lenne V-nek X és Y részhalmaza, amelyekre igazak a következők: metszetük t, egyesítésük V, mindkét halmaz legalább 2 pontú, t-t kivéve nincs él közöttük, és az X,Y halmazok által feszített részgráfok összefüggők. Mivel G minimális ellenpélda volt, azért ezek a részgráfok síkba rajzolhatók. Ha összeillesztjük őket t-nél, akkor G egy síkba rajzolását kapjuk, ami ellentmondás. Tehát G 2-összefüggő.
Állítás - G 3-összefüggő. Feltehető, hogy G-nek legalább 5 csúcsa van, mert a teljes 4-es síkba rajzolható, így a legfeljebb 4 pontú gráfok is.
Tegyük fel indirekt, hogy x,y elvágó pontpár.
Ekkor van V-nek X és Y részhalmaza, amelyekre igazak a következők: metszetük x,y, egyesítésük V, mindkét halmaz legalább 3 pontú, x,y-t kivéve nincs él közöttük, és az X,Y halmazok által feszített részgráfok összefüggők. Legyen GX az X által feszített gráf az e=xy éllel, és hasonlóan a GY az Y által feszített gráf az e=xy éllel.
G_X nem tartalmaz felosztott K3,3-at és K5-öt.
Különben az használná az új e élt, hiszen G-ben nincs felosztott K3,3 és K5. GY-ban azonban van út x és y között. Erre az útra cserélve az e élt az eredeti G gráfban is kapunk felosztott K3,3-at vagy K5-öt, ellentmondás.
Hasonlóan GY sem tartalmaz felosztott K3,3-at és K5-öt. Indukcióval GX és GY is síkbarajzolható. Ezeket összetéve az e él mentén a G síkba rajzolását kapjuk az e él esetleges hozzávételével.
3-összefüggő gráfokra a tétel következik Tutte fent említett tételéből.