Feladat: A.553 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2012/január, 30. oldal  PDF  |  MathML 
Témakör(ök): Nehéz feladat, Részgráfok, Logikai feladatok

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 egy n pontú G egyszerű gráf fokszámainak δ(G) minimuma legalább 3n/4. Bizonyítsuk be, hogy G éleinek bármely 2-színezésében van olyan legalább δ(G)+1 pontú összefüggő részgráf, melynek minden éle ugyanolyan színű.

 
 
 
 
Schweitzer-verseny, 2011 alapján