1) 
Využijte příklad z minulého týdne: Nechť $i$-tý skokan skočí $\pi(i)$-tý nejdelší skok.
Pak jeho skok je rekord, pokud (ve značení z minulého týdne) je $I_i = i$.

2) 
Využijte příklad z minulého týdne. 

3) 
Nechť $x_n$ má stupeň $d_n$. 
Uvažte komponentu $G_1$ grafu $G$, která neobsahuje vrchol $x_n$.
Ta může mít jenom stupně $< |G_1|$. 

4) 
Lze využít Hallovu větu, Mengerovu větu, toky v sítích, atd. 
Pro přímý důkaz vezměme $G'$, minimální podgraf $G$ pro který 
$\tau(G') = \tau(G)$ a ukažte, že $G'$ sestává z nezávislých hran. 

5) 
Buď $S_1$ max. nezávislá množina v $G$ a obecně $S_{i+1}$ max. nezávislá
v $G - S_1 - \dots - S_i$. Ukažte, že existuje párování z $S_{i+1}$ do $S_i$. 

6)
(a) Uvažte nejdelší cestu. Var: uvažte theta-graf, v němž bude nejkratší cestička
co nejkratší.
(b) Indukce pomocí (a).