Feladat: A.477 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2009/március, 165. oldal  PDF file
Témakör(ök): Nehéz feladat, Részgráfok, Mátrixok

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 2n pontú G teljes gráf S1,...,Sk részgráfjaira teljesülnek a következők:
(a) Mindegyik Si teljes páros gráf;
(b) G minden egyes éle páratlan sok Si-ben szerepel.
Mutassuk meg, hogy kn.