Varianty Ramseovy věty
Úloha číslo: 3786
Rozhodněte, která z následujících tvrzení jsou pravdivá:
Varianta
Pro každé přirozené \(n\) existuje přirozené \(N\) takové, že jsou-li vrcholy úplného grafu \(K_N\) obarveny dvěma barvami, potom v uvažovaném grafu je úplný podgraf \(K_n\) jehož všechny vrcholy jsou obarveny toutéž barvou.
Varianta
Obarvíme-li dostatečně velký úplný graf se smyčkami dvěma barvami (barvíme hrany a smyčky), vždy existuje jednobarevný úplný podgraf se smyčkami na \(n\) vrcholech.
Varianta
Pro každé přirozené číslo \(n\) existuje přirozené \(N\) takové, že pro libovolný graf \(G\) na \(N\) vrcholech platí: buď \(G\) obsahuje \(K_{n,n}\) jako podgraf nebo doplněk \(G\) obsahuje \(K_{n,n}\) jako podgraf. (Zmiňovaný podgraf nemusí být indukovaný.)
Varianta
Pro každé přirozené číslo \(n\) existuje přirozené \(N\) takové, že pro libovolný graf \(G\) na \(N\) vrcholech platí: buď \(G\) obsahuje \(K_{n,n}\) jako podgraf nebo \(G\) obsahuje doplněk \(K_{n,n}\) jako podgraf. (Zmiňovaný podgraf nemusí být indukovaný.)