KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4079. (March 2008)

B. 4079. Let G be a simple graph in which the longest path consists of k\ge3 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 15 April 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 p1\neq1, és tekintsük a p1p0q0q1 utat. Egészítsük ki ezt egy tovább már nem folytatható P=p_np_{n-1}\ldots p_1p_0q_0q_1\ldots q_{m-1}q_m úttá. Itt m,n\ge1 és a leghosszabb útra adott feltétel miatt n+m+1\lek, vagyis n és m közül valamelyik nem nagyobb, mint \frac{k-1}{2}. Szimmetria okok miatt feltehetjük, hogy n\le
\frac{k-1}{2}. 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 p_{n-1},\ldots,p_1,p_0 csúcsokba, mert ezek száma kisebb pn fokszámánál. így pn össze kell legyen kötve a q_0,q_1,\ldots,q_m csúcsok valamelyikével, mondjuk qi-vel, és így egy p_np_{n-1}\ldots p_1p_0q_0\ldots q_ip_n 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.

Our web pages are supported by:   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