Dvojobarvený graf
Úloha číslo: 3785
Dokažte následující variantu Ramseyovy věty: Pro každé \(n\) (velikost požadovaného podgrafu) a každé \(k\) (počet barev) existuje \(N\) takové, že pro libovolnou dvojici obarvení hran \(c_1\), \(c_2\) úplného grafu na \(N\) vrcholech (tedy funkce \(c_1,c_2: {\{1,\ldots,N\}\choose 2} \rightarrow \{1,\ldots,k\}\)) existuje úplný podgraf velikosti \(n\), který je jednobarevný jak v obarvení \(c_1\), tak v obarvení \(c_2\).
Řešení
Stačí zvolit \(N\) podle Ramseyovy věty pro grafy, \(k^2\) barev a homogenní podgraf na \(n\) vrcholech.
Libovolná dvě obarvení \(c_1\), \(c_2\) spojíme do jednoho obarvení \(c(e):=(c_1(e),c_2(e))\), což je obarvení využívající nejvýše \(k^2\) barev.
Jednobarevný podgraf vzhledem k \(c\) je jednobarevný i vzhledem k oběma obarvením \(c_1\), \(c_2\).
