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

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 P=v_1v_2\ldots v_k utat, ahol v_1,\ldots,v_k 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 3\lei\lek index, hogy u=vi, máskülönben a P utat meg lehetne hosszabbítani az uv1 éllel. Ekkor viszont C_u=v_1v_2\ldots v_iv_1 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