# 29.1.2013 - Mareš

<{ForumPost(poster="Anonymous", timestamp=2013-01-29 14:49:51)}>
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 ;-)
<{/ForumPost}>

<{ForumPost(poster="Satine", timestamp=2013-01-29 18:19:55)}>
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}$)
<{/ForumPost}>