Feladat: F.2923 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Csörnyei Marianna ,  Dienes Péter ,  Dőtsch András ,  Futó Gábor ,  Gyarmati Katalin ,  Horváth Gábor ,  Király Tamás ,  Kis Gábor ,  Kóczy László ,  Maróti Attila ,  Megyesi Zoltán ,  Mile István ,  Németh Ákos ,  Pete Gábor ,  Valkó Benedek 
Füzet: 1993/április, 159 - 160. oldal  PDF  |  MathML 
Témakör(ök): Euler-formula, Gráfelmélet, Indirekt bizonyítási mód, Feladat
Hivatkozás(ok):Feladatok: 1992/október: F.2923

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.

Tegyük fel, hogy a pontok összekötése egymást nem keresztező szakaszokkal megtörtént. A kapott alakzatot úgy tekinthetjük, mint egy csupa háromszöglap határolta egyszerű poliédernek egyik lapjára való merőleges vetületét. Erre a poliéderre alkalmazható Euler tétele, amely szerint

c+l=e+2,(1)
ahol c a csúcsok, l a lapok, e pedig az élek száma.
Tegyük fel a feladat állításával ellentétben, hogy minden csúcsból legalább 6 él indul ki. Mivel minden él két csúcsot köt össze, 2e≥6c, azaz
e3≥c.(2)
Tudjuk továbbá, hogy minden lap háromszög és egy-egy él két laphoz tartozik (feltéve, hogy nincs olyan él, amelynek valamely belső pontja is csúcs); ekkor 3l=2e, amiből
l=23e.(3)
(2) és (3) alapján (1)-ből azt kapjuk, hogy e3+23e≥e+2, azaz e≥e+2, ami ellentmondás. Ezért nem lehetséges, hogy minden csúcsból legalább 6 él induljon ki, tehát igaz a feladat állítása.
 
 

Hátra van még az az eset, amikor van olyan él, amelynek egy belső pontja is csúcs. Ilyen esetet tüntet fel az ábra. Húzzuk meg ekkor az AB élt is, illetve az AB-hez hasonló szerepű éleket. Ezután alkalmazható az előbbi gondolatmenet, és most is következik a feladat állítása.