A B. 4065. feladat (2008. február)

B. 4065. Legyen G olyan egyszerű gráf, amelyben minden csúcs foka legalább 2. Mutassuk meg, hogy van G-nek olyan csúcsa, hogy minden belőle induló él benne van egy körben.

(3 pont)

A beküldési határidő 2008. március 17-én LEJÁRT.

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 v₁ csúcsnak egy v₂-től különböző szomszédja (ilyen csúcs létezik, hiszen v₁ foka legalább 2). Ekkor van olyan 3 $\le$ i $\le$ k index, hogy u=v_i, máskülönben a P utat meg lehetne hosszabbítani az uv₁ éllel. Ekkor viszont $C_u=v_1v_2\ldots v_iv_1$ egy olyan kör lesz a gráfban, amely tartalmazza a v₁u=v₁v_i élet. Mivel pedig bármely ilyen u csúcsra a C_u kör a v₁v₂ élet is tartalmazza, minden v₁-ből induló élre teljesül, hogy az benne van egy körben.

Statisztika:

47 dolgozat érkezett.

3 pontot kapott: Á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 pontot kapott: Éles András, Frankl Nóra, Szabó 124 Zsolt, Szepesvári Dávid.

1 pontot kapott: 5 versenyző.

0 pontot kapott: 21 versenyző.

A KöMaL 2008. februári matematika feladatai

47 dolgozat érkezett.
3 pontot kapott:	Á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 pontot kapott:	Éles András, Frankl Nóra, Szabó 124 Zsolt, Szepesvári Dávid.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	21 versenyző.

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