# Zkouška Tancer 10. 1. 2025

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 množin $E \subseteq \binom{V}{2}$ rovinných grafu $G = (V,E)$, pro které $V = [n]$. 
$\newline$
Neboli $X = \{E \subseteq \binom {[n]} 2 |$ graf ([n], E) je rovinný$\}$

   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ň $\dbinom{\binom{n}{2}}{2}$. (existují i delší, stačí se však omezit na $\dbinom{\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.