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