Úkoly z diskrétní matematiky, 9. série

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

(9.1) Rozhodněte (a vaše tvrzení dokažte) pro každou kombinaci čísel n, k ∈ ℕ, zda existuje či neexistuje k-regulární graf na n vrcholech. 5 bodů

(9.2) Dokažte, že každý graf G má skorovyváženou orientaci. To znamená, že každou hranu e ∈ E(G) zorientujeme tak, že ve výsledku se pro každý vrchol v ∈ V (G) výstupní stupeň deg_{G}^{−}(v) (tedy počet hran co z v vychází) liší od vstupního stupně deg_{G}^{+}(v) (počet hran co do v vchází) nejvýše o jedna. 4 body

(9.3) Nechť T je strom. Dokažte, že T má aspoň Δ(T) listů. (Symbol Δ(G) značí maximální stupeň grafu G.) 3 body

(9.4) Dokažte, že v každém grafu G existuje cesta délky δ(G). (Symbol δ(G) značí minimální stupeň grafu G.) 2 body

(9.5) Dokažte, že v každém grafu G s δ(G) ≥ 2 existuje kružnice délky alespoň δ(G) + 1. 3 body

(9.6) Nechť n ∈ ℕ, n ≥ 2. Dokažte, že posloupnost celých čísel (d_{1}, d_{2}, …, d_{n}) je skóre nějakého stromu, právě tehdy když d_{i} > 0 pro i = 1, …, n a platí ∑_{i=1}^{n} d_{i} = 2(n − 1). 4 body

(9.7) Dokažte, že pro barevnost libovolného grafu G platí

χ(G) ≤ Δ(G) + 1.

3 body

(9.8) Devatenáct rodin si navzájem posílá novoroční přání, každá rodina jich rozešle devět ostatním (různým) rodinám. Dokažte, že existuje rodina, která dostala přání od rodiny, které sama nepřála. 3 body

(9.9) Nechť G je rovinný graf, jehož všechny stupně jsou alespoň 5. Dokažte, že G nutně musí mít alespoň 12 vrcholů. 3 body