Feladat:	B.4733	Korcsoport: 16-17	Nehézségi fok: könnyű
Megoldó(k):	Baran Zsuzsanna ,  Varjas István Péter
Füzet:	2016/április, 221. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Gráfelmélet
Hivatkozás(ok):	Feladatok: 2015/október: B.4733

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. Az egyes csúcsokhoz rendelt számok csak attól függnek, hogy hány darab 2-essel jelölt él fut be ezekbe a csúcsokba. Ha $k$ db 2-es él fut be, akkor a csúcsra írt szám $2^k$ lesz. Ezért elég a 2-essel jelölt éleket tartalmazó gráfot vizsgálni. Ez is egy $n$ csúcsú egyszerű, de nem feltétlenül összefüggő gráf lesz. Ebben a gráfban minden csúcs fokszáma a $\left\{\mathrm{0,1,}\text{...}\mathrm{,}\left(n-1\right)\right\}$ halmazból kerül ki, de nem lehet egyszerre 0 fokszámú csúcs és $n-1$ fokszámú csúcs is, hiszen ha van $n-1$ fokszámú csúcs, akkor az minden más csúccsal össze van kötve egy-egy éllel, így nem lehet 0 fokszámú csúcs. Ezek szerint az $n$ darab fokszám legfeljebb $n-1$-féle értéket vehet fel, így a skatulyaelv szerint lesz két megegyező fokszámú csúcs. Ez azt jelenti, hogy az eredeti gráfban lesz két csúcs, amibe ugyanannyi 2-essel jelölt él fut be, így ugyanannyi lesz a hozzájuk rendelt szám. Ezt akartuk belátni.