Hamiltonovská kružnice
Úloha číslo: 3790
Ukažte, že obarvíme-li libovolně hrany úplného grafu na alespoň třech vrcholech dvěma barvami, potom lze vždy nalézt hamiltonovskou kružnici takovou, že je buď celá jednobarevná, nebo její hrany lze rozdělit na dvě jednobarevné cesty.
Nápověda
Indukcí podle počtu vrcholů.
Řešení
Pro \(C_3\) tvrzení platí přímočarým rozborem dvou případů.
Předpokládejme, že tvrzení platí pro \(n-1\). Z grafu \(K_n\) odebereme libovolný vrchol \(u\) a v \(K_n\setminus u\) nalezneme patřičně obarvenou hamiltonovskou kružnici. Je-li jednobarevná, přidání \(u\) na jakékoli místo v cyklu vytvoří nejvýš jeden modrý úsek, což by byla hledená hamiltonovská kružnice v \(K_n\).
Předpokládejme proto, že hamiltonovská kružnice v \(K_n\setminus u\) se sestává ze dvou jednobarevných úseků a že \(v\) je jeden ze dvou vrcholů ležících na hranici obou barev (řekněme červené a modré). Je-li hrana \((u,v)\) červená, lze \(u\) vložit do cyklu mezi \(v\) a jeho "modrého" souseda, čímž získáme hledanou kružnici (a obráceně pro modrou hranu \((u,v)\)).