2k +1 ország k-k diplomatát küldött egy tárgyalásra. Mutasd meg, hogy leültethetők a küldöttek egy kerekasztal köré úgy, hogy bármely két ország tudjon tárgyalni egymással! (? )

2k+1 országunk van, minden országból k diplomatával, akik egy kerekasztalnál foglalnak helyet. Ha a diplomaták alkotják a gráf csúcsait, és az élek azt jelölik, hogy két diplomata egymás mellett ül, akkor értelemszerűen egy 2-reguláris gráfot kell kapnunk (mivelhogy mindenkinek 2 szomszédja van). Tehát a k darab azonos nemzetiségű diplomata 2k szomszéddal fog rendelkezni (ami pont megegyezik a maradék országok számával).

Szedjük csoportokra a küldötteket ország szerint, 2k+1 darab k elemű csoportot kapunk, amelyeken belül nincsenek kapcsolatok, így ezek lesznek a színcsoportok. Ebből már látszik, hogy a kromatikus szám 2k+1 lesz, mivel ennyi csoportunk van, és a csoportok mindegyike között lesz kapcsolat. A k darab csúcsból 2k darab élet tudunk húzni, egyet-egyet az összes többi csoportba. Ezzel egy csoportból minden lehetséges élet behúzunk, vagyis egy ország minden további országgal tud már tárgyalni. Marad 2k csoportunk, egyenként 2k-1 szabad éllel (mivel egyet mindegyikbe behúztunk). Most innen is behúzunk 1-1 élet a maradék 2k-1 csoporthoz, ezzel még egy csoportot kipipáltunk, marad 2k-1 csoport egyenként 2k-2 szabad éllel. Ezt folytatva minden 'lépésnél' 1-el kevesebb szabad él marad csoportonként, mint ahány csoport maradt kitöltetlenül, és a kitöltetlen csoportok között egyetlen él sem húzódik még a lépések után. Így amikor csak 2 csoport marad 1-1 behúzható éllel, biztosak lehetünk, hogy ez a 2 ország még nincs tárgyalási helyzetben egymással, de minden más országgal igen. Összekötve őket zárul a kör. Ebből látszik, hogy leültethetőek úgy körben, hogy minden ország minden országgal tudjon kommunikálni.