Az A. 309. feladat (2003. január)

A. 309. Egy \(\displaystyle n\) csúcsú egyszerű gráfban a csúcsok fokszámai rendre \(\displaystyle 0<d_1\le \dots\le d_n\). Bizonyítsuk be, hogy kiválasztható legalább \(\displaystyle \sum \frac{2}{d_i+1}\) csúcs úgy, hogy az általuk kifeszített részgráfban nincs kör.

(5 pont)

A beküldési határidő 2003. február 15-én LEJÁRT.

Statisztika:

9 dolgozat érkezett.
5 pontot kapott:	Csóka Endre, Kiss Demeter, Kunszenti-Kovács Dávid, Nagy 444 Zoltán, Rácz Béla András.
4 pontot kapott:	Hablicsek Márton, Paulin Roland.
3 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2003. januári matematika feladatai