A B. 4725. feladat (2015. szeptember)

B. 4725. Mutassuk meg, hogy ha egy egyszerű gráfnak 7 csúcsa van és nincs 4 hosszú köre, akkor van olyan csúcsa, aminek a foka legfeljebb 2.

(4 pont)

A beküldési határidő 2015. október 12-én LEJÁRT.

Megoldásvázlat. A feladat feltétele azt jelenti, hogy két különböző csúcsnak legfeljebb egy közös szomszédja lehet.

Indirekt tegyük föl, hogy minden pont foka legalább 3. Válasszunk egy $\displaystyle X$ csúcsot és annak három szomszédját - utóbbiak halmazát jelölje $\displaystyle S$. Ekkor $\displaystyle S$ elemei között összesen legfeljebb egyetlen él halad, így $\displaystyle S$ elemeinek $\displaystyle X$-től különböző, $\displaystyle S$-en kívül eső szomszédjai legalább $\displaystyle 1+1+2=4$ további csúcsot adnának, ami ellentmondás.

Statisztika:

158 dolgozat érkezett.
4 pontot kapott:	119 versenyző.
3 pontot kapott:	15 versenyző.
2 pontot kapott:	8 versenyző.
1 pontot kapott:	12 versenyző.
0 pontot kapott:	3 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2015. szeptemberi matematika feladatai