Kezdőlap


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

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 $A_{1}$ -gyel és $A_{2}$ -vel, $B$ másik két szomszédját pedig $B_{1}$ -gyel és $B_{2}$ -vel. Ekkor $A_{1}$ , $A_{2}$ , $B_{1}$ és $B_{2}$ 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 $A_{1}$ -nek és $A_{2}$ -nek vagy $B_{1}$ -nek és $B_{2}$ -nek, illetve az egyik $A_{i}$ -nek, a másik $B_{j}$ -nek szomszédja (1. ábra). Ez összesen további $4 \cdot 2 = 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 (

A_{3}

A_{4}

A_{5}

A_{6}

B_{3}

B_{4}

B_{5}

B_{6}

) szomszédainak kiválasztásakor arra kell figyelni, hogy az

A_{i}

típusú csúcsok mindkét szomszédja

B_{j}

típusú legyen és ráadásul az egyik

B_{1}

-nek, a másik pedig

B_{2}

-nek legyen szomszédja, valamint ugyanez igaz legyen a

B_{i}

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