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

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze