Úkoly z Kombinatoriky a grafů, 10. série

Veškerá tvrzení precizně zdůvodněte.

(10.1) Nechť G je rovinný vrcholově 2-souvislý graf a uvažme libovolné jeho rovinné nakreslení. Pořádně dokažte, že hranice každé stěny (i té vnější) je grafová kružnice. 3 body

(10.2) Dokažte, že ve vrcholově 2-souvislém grafu pro každé dvě hrany existuje kružnice, která je obsahuje. 4 body

(10.3) Existuje hranově 2-souvislý graf, kde nějaké dvě jeho hrany neleží na kružnici? 3 body

(10.4) Dokažte či vyvraťte: Pro každé n ∈ ℕ existuje N ∈ ℕ, že jsou-li hrany úplného grafu K_{N} libovolně obarveny n barvami, potom v uvažovaném K_{N} existuje úplný podgraf K_{n}, jehož všechny hrany mají tutéž barvu. 3 body

(10.5) Dokažte či vyvraťte: Pro všechna n, p ∈ ℕ existuje N ∈ ℕ, že je-li X libovolná N-prvková množina, jejíž každá neprázdná podmnožina velikosti nanejvýš p je obarvena jednou ze dvou barev, potom existuje n-prvková podmnožina Y ⊆ X, jejíž všechny podmnožiny velikosti nejvýš p mají tutéž barvu. 3 body

(10.6) Dokažte, že pro každé k ∈ ℕ existuje N ∈ ℕ takové, že libovolná N-prvková posloupnost reálných čísel obsahuje neklesající nebo nerostoucí podposloupnost délky k. 5 bodů