Ramseyova věta pro dvoubarevný graf

Úloha číslo: 3784

Dokažte, že pro každé \(k \in \mathbb N\) existuje \(n \in \mathbb N\) takové, že pro každý graf \(G=(V,E)\) s alespoň \(n\) vrcholy a každé jeho obarvení hran \(c:E \rightarrow \{1{,}2\}\) existuje \(U \subseteq V\) velikosti alespoň \(k\) taková, že všechny hrany indukovaného podgrafu \(G[U]\) mají stejnou barvu.

  • Řešení

    Doplníme nehrany a obarvíme je libovolně. Pak aplikujeme klasickou Ramseyovu větu pro dvě barvy v úplném grafu.

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