Egy n pont teljes gráfban miért biztos, hogy ha random kiszínezzük az éleket, lesz egyszínű Hamilton-út?

Másként; vegyünk egy turnamentgráfot: olyan irányított gráf, ahol minden csúcs mindenkivel össze van kötve irányított éllel; ez a gráf szimbolizálja egy n tagú osztály magassággráfját; a magasabbtól mutasson nyíl az alacsonyabbra, például ha Dani nagyobb, mint Peti, akkor D->P, ha Viktor kisebb, mint Józsi, akkor V<-J, azt még megkötjük, hogy mindenki magassága különböző.

Nem nehéz kitalálni, hogy tetszőleges osztályban tudunk tornasort kialakítani, ahol minden ember a legnagyobbat és a legkisebbet leszámítva mindig egy nagyobb és egy kisebb ember mellett áll. Ez a tornasor mutatja a turnamentgráf Hamilton-útját. Persze ez nem egy precíz bizonyítás, de a megértéshez elég.

A színezésnél is ugyanez a helyzet.

Utánagondoltam, és rájöttem, hogy nem igaz az állítás, mivel találtam ellenpéldát.

n≥4-re színezzük a következő szerint az éleket: válasszuk ki egy csúcsát, és a belőle induló összes élt színezzük pl. pirosra, az összes többi élt kékre. Ha a pirossal színezett éleket tekintjük, akkor egy csillagot látunk, aminek n-1 darab elsőfokú éle van, ez n≥4-re legalább 3 darab, így piros élű Hamilton-út nincsen, mivel ha van, akkor legfeljebb 2 elsőfokú csúcsa lehet. Ha a kékkel színezett gráfot vizsgáljuk, akkor látjuk, hogy nemhogy Hamilton-út nincs benne, de még csak nem is összefüggő a gráf, mivel az előbb kiválasztott csúcs itt izolált csúcsként fog kinézni.

3≥n-re igaz az állítás, és mivel nincs belőle túl sok színezés (összesen 1+1+2+8=12), ezért ezt úgy is lehet bizonyítani, hogy az összes színezést bemutatjuk, és könnyen látható, hogy igaz.