A C. 1412. feladat (2017. március)

C. 1412. Mely \(\displaystyle n\) természetes számok esetén létezik olyan \(\displaystyle n\) csúcsú, \(\displaystyle 2n\) élű, síkba rajzolható egyszerű gráf, melynek tartományai nem színezhetők ki két színnel úgy, hogy az élben szomszédos tartományok különböző színűek legyenek?

(5 pont)

A beküldési határidő 2017. április 10-én LEJÁRT.

Megoldás. Egy \(\displaystyle n\) csúcsú egyszerű gráfnak legfeljebb \(\displaystyle \binom n2\) éle van. Az 1 csúcsú gráfnak nincs éle. Mivel \(\displaystyle \binom22=1<2\cdot2\), \(\displaystyle \binom32=3<2\cdot3\), \(\displaystyle \binom42=6<2\cdot4\), ezért \(\displaystyle n\leq4\) esetén biztosan nincs megfelelő gráf. Mivel \(\displaystyle \binom52=10=2\cdot5\), azért \(\displaystyle n=5\) esetén a gráf összes élét be kell rajzolni. Az öt csúcsú teljes gráfban, ha síkbarajzolható lenne, akkor az Euler-formula szerint 7 tartománynak kellene lennie (most a nagy tartományt is beleszámítjuk). Mivel minden tartományhoz legalább 3 él tartozik, és minden él pontosan két tartományhoz tartozik, ezért az élek számára \(\displaystyle \frac{3\cdot7}{2}\) egy alsó becslést ad, ami ellentmondás, hiszen csak 10 él van. Tehát az 5 csúcsú teljes gráfot nem tudjuk síkbarajzolni.

Legyen most \(\displaystyle n\geq6\). Legyen a gráf felépítése a következő:

A \(\displaystyle P_1\) pont egy kör középpontja, a \(\displaystyle P_2\), \(\displaystyle P_3\), \(\displaystyle P_4\), \(\displaystyle P_5\) \(\displaystyle P_6\),...\(\displaystyle P_n\) pontok pedig ebben sorrendben a körvonalon helyezkednek el. A \(\displaystyle P_1\) pontot kössük össze az összes többi ponttal, és a körvonal szomszédos pontjait is kössük össze egy-egy szakasszal. Ez eddig \(\displaystyle 2(n-1)\) él. Végül kössük össze \(\displaystyle P_2\)-t és \(\displaystyle P_4\)-et, illetve \(\displaystyle P_4\)-et és \(\displaystyle P_6\)-ot. Ekkor a \(\displaystyle P_1P_2P_3\), \(\displaystyle P_2P_3P_4\) és \(\displaystyle P_3P_4P_1\)tartományok páronként szomszédosak, így 3 szín szükséges a megfelelő színezésükhöz.

Tehát \(\displaystyle n\geq6\) esetén létezik megfelelő gráf.

Statisztika:

28 dolgozat érkezett.
5 pontot kapott:	Édes Lili, Németh Csilla Márta, Rittgasszer Ákos, Surján Anett, Szécsi Adél Lilla, Zsombó István.
4 pontot kapott:	Kocsis Júlia, Mácz Andrea, Nagy Olivér, Szilágyi Éva, Tatai Mihály.
3 pontot kapott:	9 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2017. márciusi matematika feladatai