1. (a) 
Ještě jeden přídavek: nakreslete graf částečných součtů a podívejte se
na jeho konvexní obal. 

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. Uvažte maximální cyklus. 

3. Napřed to zkuste pro $r$-regulární grafy, indukcí podle $r$. 

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. Jinak by $H$ byl úplně vyvážený! 

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.