Příklad 1. Mějme 3 přirozená čísla $k$, $\ell$, $m$ taková, že nejvýše jedno z nich je rovno jedné. Mějme graf, který obsahuje vrcholy $u$, $v$, a 3 disjunktní cesty mezi těmito vrcholy, které mají popořadě $k$. $\ell$ a $m$ hran (a tento graf již neobsahuje nic dalšího). Kolik má tento graf koster?
(2 body)
Příklad 2. Mějme graf $G$, jeho kostru $K$ a jeho hranu $e$, která není součástí $K$. Dokažte, že existují alespoň 2 různé hrany $e',e''\in K$ takové, že $K$ po přidání $e$ a odebrání libovolné z hran $e',e''$ je stále kostra G.
(2 body)
Příklad 3. Mějme souvislý graf $G$ na alespoň 3 vrcholech. Dokažte, že existují 2 vrcholy $u$, $v$ takové, že $G\setminus \{u\}$, $G\setminus\{v\}$ i $G\setminus \{u,v\}$ jsou souvislé.
(3 body)
Příklad 4. Najděte souvislý graf $G(V,E)$ na alespoň 4 vrcholech takový, že pro každou tříprvkovou množinu jeho vrcholů $M\subset V, |M| = 3$ platí, že existuje $M'\subseteq M$ taková, že $G\setminus M'$ souvislý není.
(1 bod)