Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem C. 1412. (March 2017)

C. 1412. For what natural numbers \(\displaystyle n\) is there a simple planar graph of \(\displaystyle n\) points and \(\displaystyle 2n\) edges in which the faces cannot be coloured in two colours so that faces with an edge in common should have different colours?

(5 pont)

Deadline expired on April 10, 2017.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

28 students sent a solution.
5 points:Édes Lili, Németh Csilla Márta, Rittgasszer Ákos, Surján Anett, Szécsi Adél Lilla, Zsombó István.
4 points:Kocsis Júlia, Mácz Andrea, Nagy Olivér, Szilágyi Éva, Tatai Mihály.
3 points:9 students.
2 points:5 students.
1 point:2 students.
0 point:1 student.

Problems in Mathematics of KöMaL, March 2017