29.1.2013 - Mareš

1. Věta o pěti barvách + důkaz

2. Erdős - Szekeresovo lemma + důkaz

3. Dokázat, že pro každý graf platí: pro všechny v z $V(G): \deg(v) \ge d$, potom v grafu existuje cesta délky d

4. Kolik existuje permutací z množiny {1_n} s k pevnými body

Naprosto pohodová zkouška, není se čeho bát ;-)

Otázky z odpoledne:

1. Princíp inkluze a exkluze + důkaz

2. Dokázat ekvivalenci: (d1, d2, ..., dn) je skóre stromu $\iff \sum_{i=1, \ldots, n} di = 2n - 2$

3. Dokázat ekvivalenci: V(G) = E(G) + (počet komponent G) <=> graf G je les

4. Kolik je asymetrických relací na množině $\{1, \ldots, n\}$ (je jich $2^n \cdot 3^{(n^2 - n)/2}$)