Problem B. 4065. (February 2008)
B. 4065. Let G be a simple graph in which the degree of every vertex is at least 2. Show that G has a vertex, such that every edge drawn from that vertex belongs to a circuit.
(3 pont)
Deadline expired on March 17, 2008.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás: Tekintsünk G-ben egy maximális utat, ahol a gráf (különböző) csúcsai. Legyen u a v1 csúcsnak egy v2-től különböző szomszédja (ilyen csúcs létezik, hiszen v1 foka legalább 2). Ekkor van olyan 3ik index, hogy u=vi, máskülönben a P utat meg lehetne hosszabbítani az uv1 éllel. Ekkor viszont egy olyan kör lesz a gráfban, amely tartalmazza a v1u=v1vi élet. Mivel pedig bármely ilyen u csúcsra a Cu kör a v1v2 élet is tartalmazza, minden v1-ből induló élre teljesül, hogy az benne van egy körben.
Statistics:
47 students sent a solution. 3 points: Ágoston Tamás, Bodor Bertalan, Bóra Eszter, Bunth Gergely, Fonyó Dávid, Fukker Gábor, Gévay Gábor, Horváth 385 Vanda, Nguyen Milán, Palincza Richárd, Peregi Tamás, Réti Dávid, Salát Zsófia, Strenner Péter, Szalkai Balázs, Szőke Nóra, Varga 009 Bálint. 2 points: Éles András, Frankl Nóra, Szabó 124 Zsolt, Szepesvári Dávid. 1 point: 5 students. 0 point: 21 students.
Problems in Mathematics of KöMaL, February 2008