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})