Ramseyova věta pro vrcholy
Úloha číslo: 3656
Dokažte, že pro každé přirozené \(k\) existuje přirozené \(n\) s následující vlastností. Jsou-li vrcholy úplného grafu \(K_n\) obarveny 14 barvami, potom existuje \(k\) vrcholů, které mají stejnou barvu.
Řešení
Podle Dirichletova principu stačí vzít \(n=14k-13\), potom některá ze 14 podmnožin bude obsahovat alespoň \(k\) vrcholů.
Hrany grafu zde nejsou podstatné.
