Feladat: B.4763 Korcsoport: 16-17 Nehézségi fok: átlagos
Kitűző(k):  Mészáros Gábor 
Füzet: 2016/január, 34. oldal  PDF file
Témakör(ök): Feladat, Gráfelmélet, Számhalmazok, Teljes indukció módszere
Hivatkozás(ok):Feladatok megoldásai: 2016/szeptember: B.4763

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.

Legyen G egy n csúcsú, irányítatlan, egyszerű gráf. Igazoljuk, hogy megadhatóak a gráfhoz a természetes számok olyan végtelen H1,H2,...,Hn részhalmazai, amelyekre bármely két részhalmaz metszete végtelen, ha a hozzájuk tartozó csúcsok éllel összekötöttek, és üres, ha nincs él a megfelelő csúcsok között.