Feladat: N.128 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 1997/február, 100. oldal  PDF  |  MathML 
Témakör(ök): Gráfelmélet, Gráfok összefüggősége, Fagráfok, erdők, faváz, Nehéz feladat

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.

Adott a síkon n pont, semelyik három sincs egy egyenesen. Megrajzoljuk az összes általuk meghatározott szakaszt, és mindegyik szakaszt kiszínezzük két szín valamelyikével. Igazoljuk, hogy a kapott gráfban létezik egyszínű feszítő fa, amelynek élei nem metszik egymást. (Feszítő fán olyan összefüggő és körmentes gráfot ‐ azaz fát ‐ értünk, amelynek csúcsai éppen az eredeti gráf csúcsai, élei pedig az eredeti gráf bizonyos élei.)