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

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

(10.1) Dokažte, že úplný bipartitní graf K_{n,m} je rovinný právě tehdy, když

min{n, m} ≤ 2.

3 body

(10.2) Dokažte, že barevnost rovinných grafů bez trojúhelníku je 4, a to bez pomoci věty o čtyřech barvách. Hint: dokažte, že každý takový graf je 3degenerovaný. 6 bodů

(10.3) Nechť G je graf. Dokažte následující vztah:

χ(G) · α(G) ≥ |V (G)|,

kde χ(G) značí chromatické číslo a α(G) velikost největší nezávislé množiny v G. 5 bodů

(10.4) Precizně dokažte, že graf je rovinný, právě když každé jeho dělení je rovinné.

2 body

(10.5) Kolik koster má úplný bipartitní graf K_{2,n}? 4 body (10.6) Nechť G je souvislý graf. Dokažte, že pro každou hranu e ∈ E(G) existuje

kostra K grafu G, která hranu e obsahuje. 4 body