Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 4079. feladat (2008. március)

B. 4079. Legyen G olyan egyszerű gráf, amelyben a leghosszabb út k\ge3 élből áll, és minden csúcs foka legalább k/2. Mutassuk meg, hogy G-nek minden éle benne van egy körben. (Útnak nevezzük egymáshoz csatlakozó élek egy olyan sorozatát, amely minden csúcsot legfeljebb egyszer érint.)

Javasolta: Héger Tamás (Budapest)

(4 pont)

A beküldési határidő 2008. április 15-én LEJÁRT.


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.


Statisztika:

21 dolgozat érkezett.
4 pontot kapott:É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 pontot kapott:Kiss 716 Eszter.
2 pontot kapott:1 versenyző.
1 pontot kapott:3 versenyző.
0 pontot kapott:1 versenyző.

A KöMaL 2008. márciusi matematika feladatai