Feladat: B.3807 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Kiss Réka 
Füzet: 2005/december, 538 - 540. oldal  PDF file
Témakör(ök): Gráfelmélet, Feladat
Hivatkozás(ok):Feladatok: 2005/március: B.3807

Legalább hány csúcsa van egy olyan gráfnak, amelyben nincs 6-nál rövidebb kör és minden csúcsának a foka 3?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Megmutatjuk, hogy a gráfnak legalább 14 csúcsa van, és 14 csúcsú, a feltételeknek megfelelő gráf van is.
Legyen A és B a gráf két olyan csúcsa, melyeket él köt össze. Ekkor A-ból is és B-ből is még két-két él indul ki. Ezek végpontjai különbözőek, mert ha közülük valamelyik kettő egybeesne, akkor a gráfban lenne 3 hosszú kör. Jelöljük A másik két szomszédját A1-gyel és A2-vel, B másik két szomszédját pedig B1-gyel és B2-vel. Ekkor A1, A2, B1 és B2 további két-két szomszédja mind különböző csúcs kell hogy legyen, mert ha közülük valamelyik kettő egybeesne, akkor a gráfban lenne 4 vagy 5 hosszú kör, attól függően, hogy a közös szomszéd A1-nek és A2-nek vagy B1-nek és B2-nek, illetve az egyik Ai-nek, a másik Bj-nek szomszédja (1. ábra). Ez összesen további 42=8 csúcs, tehát a gráfnak legalább 2+4+8=14 csúcsa van.

 
 

1. ábra
 

14 csúcsú jó gráf létezik, ilyen látható a 2. ábrán. Az utolsó nyolc csúcs (A3, A4, A5, A6, B3, B4, B5, B6) szomszédainak kiválasztásakor arra kell figyelni, hogy az Ai típusú csúcsok mindkét szomszédja Bj típusú legyen és ráadásul az egyik B1-nek, a másik pedig B2-nek legyen szomszédja, valamint ugyanez igaz legyen a Bi típusú csúcsokra is.
 
 

2. ábra
 

 
Megjegyzés. Megmutatható, hogy a feltételeknek megfelelő, 14 csúcsú gráf izomorfia erejéig egyértelmű (tehát a 4. és az 5. ábrán lényegében ugyanazt láthatjuk). Ezt a gráfot Heawood-gráfnak nevezik, legismertebb előállítása a 3. ábrán látható Fano síkhoz kapcsolódik (a Fano síkról Schmidt Tamás: Geometriai terek az algebra szemszögéből (KöMaL 2004/4, 199‐206. oldal) c. cikkének bevezetőjében olvashatunk). A sík 7 pontja és 7 egyenese adja a gráf 14 csúcsát. Két csúcsot pontosan akkor köt össze él, ha az egyik egyenesnek, a másik pedig valamely arra illeszkedő pontnak megfelelő csúcs. Mivel a sík minden egyenesén 3 pont van és minden ponton át 3 egyenes megy, a gráfban minden pont foka 3. A gráf definíciójából következően páros (az egyik osztályban a sík pontjainak, a másikban pedig a sík egyeneseinek megfelelő csúcsok vannak), ezért nincs benne páratlan hosszú kör. Négy hosszú kör sincs a gráfban, ellenkező esetben ugyanis volna a síkon két különböző pont, melyeknek két különböző összekötő egyenese lenne.
 
 

3. ábra
 

 
 

4. ábra
 

 
 

5. ábra