Problem B. 4079. (March 2008)
B. 4079. Let G be a simple graph in which the longest path consists of k3 edges and the degree of each vertex is at least k/2. Show that every edge of G belongs to a circuit. (A path is a sequence of linking edges that visits each vertex at most once.)
Suggested by T. Héger, Budapest
(4 pont)
Deadline expired on April 15, 2008.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás: Tekintsünk a gráfban egy p0q0 élet. A fokszám feltétel miatt vannak olyan p0-tól és q0-tól különböző p1 és q1 csúcsok, hogy p0p1 és q0q1 is éle a gráfnak. Ha p1=q1, akkor a p0q0 él benne van egy 3 hosszú körben. Tegyük fel tehát, hogy p1q1, és tekintsük a p1p0q0q1 utat. Egészítsük ki ezt egy tovább már nem folytatható úttá. Itt m,n1 és a leghosszabb útra adott feltétel miatt n+m+1k, vagyis n és m közül valamelyik nem nagyobb, mint . Szimmetria okok miatt feltehetjük, hogy . A pn csúcs foka legalább k/2, és P maximalitása folytán csak P csúcsaival lehet összekötve. Nem vezethet az összes él a csúcsokba, mert ezek száma kisebb pn fokszámánál. így pn össze kell legyen kötve a csúcsok valamelyikével, mondjuk qi-vel, és így egy kör keletkezik, amely tartalmazza a p0q0 élet.
Statistics:
21 students sent a solution. 4 points: Éles András, Kalina Kende, Keresztfalvi Tibor, Kiss 243 Réka, Kiss 902 Melinda Flóra, Lovas Lia Izabella, Nagy 648 Donát, Perjési Gábor, Réti Dávid, Strenner Péter, Tossenberger Anna, Tóth 369 László Márton, Tubak Dániel, Varga 171 László, Zieger Milán. 3 points: Kiss 716 Eszter. 2 points: 1 student. 1 point: 3 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, March 2008