Grötzschman

Kretén magazin 2004/4 száma:

• Ön milyen man szeretne lenni, és mit csinálna akkor, ha Ön szuperhős lenne, mi lenne a neve és milyen szuperképességekkel rendelkezne?

• Én bizony Grötzschman lennék, és ha bárhol a világon valakinek gondjai adódnának a Mycielski-konstrukcióval, illetve a Grötzsch-grágokkal, akkor előtűnnék a semmiből és megoldanám minden problémájukat.

Síkba-rajzolható-e a Grötzsch-gráf?

(azaz le tudjuk-e rajzolni úgy, hogy nincs benne kereszteződés)

Az ábrán látható Grötzsch gráf nem lesz síkbarajzolható. A belátáshoz K5 –öt, K3,3 –at vagy ezek soros bővítését keressük a gráfban. A K5 –öt nem találunk, de a remény még megvan a K3,3 –ra, vagy soros bővítésére. Ezt meg is találjuk. A kutakat jelölhetjük fekete pontokkal, a házakat szürkékkel. A fehéren maradt pontok, pedig  a soros bővítést jelentik. Mivel megtaláltuk a három ház – három kút gráf soros bővítését, nem lesz síkbarajzolható a Grötzsch gráf.

megjegyzés:

Definíció. A K5 és a K3,3 gráfokat Kuratowski-gráfoknak nevezzük. A K5 az 5 pontú teljes gráf. A  K3,3 gráfot szokás  három ház – három kút gráfnak is nevezni. Az elnevezés onnan ered, hogy a gráf csúcsai olyanok, mint három ház és (velük szemben) három kút. Az élei pedig az utak, melyek minden házat összekötnek minden kúttal. Láthatjuk, hogy az utakat kereszteződések nélkül nem lehet lerajzolni. Tehát a gráfban lesznek egymást 

keresztező élek. Azt, hogy a K3,3 és a K5 esetében sem lehet az éleket kereszteződés nélkül lerajzolni a síkba.

Tétel: A Kuratowski-gráfok nem rajzolhatóak síkba.

Tétel: (Kuratowski-tétel). Egy G gráf akkor és csak akkor síkbarajzolható, ha nem  

tartalmazza részgráfként a K5 és a K3,3 gráfokat, sem ezek soros bővítéseit.