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)\)).

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze