1. Uvědtě definici $k$-degenerovaného grafu. Uvědtě příklad $3$-degenerového grafu, který není $2$-degenerovaný. (5 bodů)

2. Kolik existuje funkcí $f: [n] \to \binom{n}{2}$ takových, že $\forall i \in [n]: i \notin f(i)$ (6 bodů)

3. Uvažujme ČUM $P = (X, \subseteq)$, kde $X$ je množina všech hran $E \subseteq \binom{V}{2}$ rovinných grafu $G = (V,E)$, pro které $V = [n]$.

   a) Najděte řetězec v $P$ s maximální velikostí a zdůvodnětě, že neexistuje řetězec s vetší delkou

   b) Pro $n \geq 3$ najděte antiřetězec s velikostí alespoň $\binom{\binom{n}{2}}{2}$. (existují i delší, stačí se však omezit na $\binom{\binom{n}{2}}{2}$)

   Pokud se vám nedaří vyřešit jednu z možností, vyřešte pro $n=5$. (9 bodů)

4. Uvědtě definici a důkaz věty o sledů (se závislosti na matici sousednosti grafu $G$) (10 bodů)

Za zkoušku bylo možné získat 30, bodů. Známkování bylo následující 1: 24-30b; 2: 20-23b; 3: 16-19b; 3$^-$: 11-15b; 4: 0-10b. Po písemné zkoušce bylo možné si zlepšit známku 2 až 3$^-$ o stupeň lepší (1 až 3) na ústní zkoušce. V případě známky 3$^-$ byla zkouška povinná. Explicitně bylo řečeno, že není možné si na ústní zkoušce zhoršit známku.