Feladat: A.508 Korcsoport: 18- Nehézségi fok: nehéz
Kitűző(k):  Lovász László Miklós 
Füzet: 2010/április, 228. oldal  PDF  |  MathML 
Témakör(ök): Nehéz feladat, Részgráfok, Részhalmazok, Konstruktív megoldási módszer

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.

A G gráfnak egy S feszített részgráfját ,,dominánsnak'' nevezzük, ha G minden S-en kívüli csúcsának van szomszédja S-ben. Létezik-e olyan gráf, aminek páros számú számú domináns részgráfja van?