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

B. 4079. Legyen G olyan egyszerű gráf, amelyben a leghosszabb út k $\ge$ 3 é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 p₀q₀ élet. A fokszám feltétel miatt vannak olyan p₀-tól és q₀-tól különböző p₁ és q₁ csúcsok, hogy p₀p₁ és q₀q₁ is éle a gráfnak. Ha p₁=q₁, akkor a p₀q₀ él benne van egy 3 hosszú körben. Tegyük fel tehát, hogy p₁ $\ne$ q₁, és tekintsük a p₁p₀q₀q₁ 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 $\ge$ 1 és a leghosszabb útra adott feltétel miatt n+m+1 $\le$ k, 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 p_n 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 p_n fokszámánál. így p_n össze kell legyen kötve a $q_0,q_1,\ldots,q_m$ csúcsok valamelyikével, mondjuk q_i-vel, és így egy $p_np_{n-1}\ldots p_1p_0q_0\ldots q_ip_n$ kör keletkezik, amely tartalmazza a p₀q₀ é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

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ő.

Már regisztráltál?
Új vendég vagy?