KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

This problem is for grade 11 - 12 students only.

Deadline expired on 10 April 2017.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem C. 1412.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley