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!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 3807. The degree of each vertex of a graph is equal to 3 and it is also given that the graph does not contain cycles whose length is less than 6. Find the lowest possible number of vertices in such a graph.

(5 points)

Deadline expired on 15 April 2005.


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

Megoldás. Ha egy gráfban nincs kör, akkor van elsőfokú csúcsa, ez tehát nem lehetséges. Jelölje g a legrövidebb kör hosszát. Ebben a C=v_1v_2\ldots v_g körben semelyik átló nem lehet behúzva. Mindegyik vi csúcsnak van tehát egy harmadik szomszédja a körön kívül. Ha ezek közül kettő egybeesne, akkor a gráfban keletkezne g-nél rövidebb kör. A gráfnak tehát legalább 14 csúcsa van, ha g\ge7. Megmutatjuk, hogy g=6 esetén is legalább 14 csúcs van. Valóban, ha a vi csúcs harmadik szomszédját wi jelöli, akkor a w_1,w_2,\ldots,w_6 csúcsok között legfeljebb három él lehet behúzva, nevezetesen w1w4, w2w5 és w3w6. Mivel ezek is harmadfokú csúcsok, mindegyikből kell még vezessen él egy eddig még nem tekintett csúcsba. Ez legalább 6 él, amihez legalább két új végpontnak kell csatlakozni, vagyis a gráfnak valóban legalább 14 csúcsa van ebben az esetben is.

Ez a gondolatmenet elvezet minket ahhoz is, hogy egy pontosan 14 csúccsal rendelkező megfelelő gráfot találjunk, sőt azt is mutatja, hogy az ábrán látható gráfon kívül más 14 csúcsú gráf nem is jöhet szóba. (Ez a gráf tehát rengeteg szimmetriával rendelkezik, hiszen bármelyik 6 hosszúságú köréből kiindulhattunk volna.)

Könnyű ellenőrizni, hogy ez a gráf nem tartalmaz 6-nál rövidebb kört, ennek részletes indoklását már az olvasóra bízzuk.


Statistics on problem B. 3807.
82 students sent a solution.
5 points:51 students.
4 points:7 students.
3 points:6 students.
2 points:2 students.
1 point:2 students.
0 point:14 students.


  • Problems in Mathematics of KöMaL, March 2005

  • 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