Příklad 1. Rozmyslete si, že graf má kostru, právě když je souvislý.
Příklad 2. Pro která $n \in \mathbb N_0$ existuje graf s právě $n$ kostrami? Pozor, v této úloze $n$ nijak nesouvisí s počtem vrcholů grafu.
Příklad 3. Ukažte, že každý strom na alespoň 3 vrcholech, který neobsahuje vrchol stupně 2, má více listů než vnitřních vrcholů.
Příklad 4. Mějme les na $n$ vrcholech, který má $m$ hran. Víme, že všechny lesy jsou bipartitní. Kolika způsoby lze (v závislosti na $n$ a $m$ rozdělit jeho vrcholy do dvou partit? Rozdělení lišící se pouze prohozením partit považujeme za stejná.
Příklad 5. Hranový graf grafu $G(V,E)$, který má alespoň jednu hranu, je graf $L(G)(E,E')$ tak, že $e_1e_2 \in E' \Leftrightarrow e_1\cap e_2\neq \emptyset$, tedy vrcholy jsou původní hrany a hrany spojují vrcholy reprezentující hrany, co měly společný vrchol. Pro jaké grafy platí, že $L(G)$ je strom? A pro jaké grafy platí, že $L(G)=G$? Najděte dva různé souvislé grafy jímž odpovídá tentýž hranový graf.
Příklad 6. Nechť $n$ je přirozené číslo. Určete počet různých koster následujících grafů: Pozor, různé kostry skutečně musí být různé, ale nevadí, když jsou izomorfní.
Příklad 7. Mějme strom $G(V,E)$ a nějaký jeho automorfismus $f$. Dokažte, že buď existuje vrchol $v$ takový, že $f(v)=v$, nebo dva vrcholy $u$, $v$ takové, že $f(u)=v$ a $f(v)=u$.
Příklad 8. Mějme strom $G$ a několik (alespoň 2) jeho souvislé podgrafy $G_1(V_1,E_1),G_2(V_2,E_2),\dots,G_n(V_n,E_n)$. Dokažte,