1. (a) 
Dva přídavky od minula: použijte tvrzení z prvního týdne (o autu na
kruhové dráze). Dále: není třeba hledat přimo bijekci mezi permutacemi. 
(To taky jde, ale je potřeba navíc předpokládat, že $x_1$, \dots, $x_n$
jsou nezávislá nad $\Z$ -- rovnice $\sum_i a_i x_i = 0$ je platná jen pokud
jsou všechna $a_i=0$. A důkaz je pak trošku jiný než je dále napovězeno.)

Nazvěme posloupnost $j_1, j_2, ..., j_k$  (navzájem různých čísel z 1, ..., n)
_rostoucí_ pokud
a) x_{j_1} + ... + x_{j_k} > 0 
b) x_{j_1} + ... + x_{j_l} <= 0 pro všechna l 0.)

Posloupnost nazveme _klesající_ pokud 
a) x_{j_1} + ... + x_{j_k} <= 0 
b) x_{j_l} + ... + x_{j_k} > 0 pro všechna l>1.
(Všimněte si drobných rozdílů!)
Rozdělte x_1, ..., x_n na rostoucí a klesající posloupnosti a pomocí toho rozdělení
vytvořte vhodné permutace, pro něž budete rozumět číslům a(), b().

(b) Užijte část (a), kde n=2m, polovina x_i je +1 a polovina -1.

2. (a,b,c) Pokud $F$ je minimální množina hran, jejíž otočení/kontrakce vede k digrafu
s požadovanou vlastností, tak otočení $F$ vede k této vlastnosti také.
(b) Uvažte napřed případ $|F|=1$.
(c) Ukažte, že vrcholy acyklického digrafu $G$ lze uspořádat tak, že každá hrana
vede z menšího vrcholu do většího.

3. V rozkladu z minulého týdne nemůže mít poslední přidávaná cesta délku 1. 

4. 
(a) Uvědomte si (a užijte), že (1,1,...,1) je vlastní vektor, a že 
    vlastní vektory k různým vlastním čislům jsou ortogonální. 
(b) Buď vlastní vektory uhodněte, nebo využijte vztahu mezi 
    maticí incidence vrcholů a hran v B, a maticí sousednosti
    grafů G a L(G). (A_G = B^T B - d.I, A_{L(G)} = B B^T - 2I). 
(c) Petersenův graf je doplněk hranového grafu K_5. 

5. Uvažte cyklus a v něm hranu--cestu, která první skončí. 


6. (a) Pro $r=2$ to už víme. Užijte indukci podle $a_1 + \dots + a_k$ a $r$.
(b) Vyberte uspořádanou $m$-tici $(x_1, \dots, x_m)$ t.ž. pro každou $r$-tici
indexů $1 \le i_1 < i_2 < \dots < i_r \le m$ mají všechny $(r+1)$-tice
$(x_{i_1}, x_{i_2}, \dots, x_{i_r}, x_t)$ (pro $i_r < t \le m$) 
stejnou barvu.