1. (a) 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. Podobně jako minule ... 

3. Jeden směr je snadný pomocí výsledku z minulého týdne. Pro druhý zvolte nějaké 
párování F, jedna hrana z F budiž G_0, a cesty P_i buďte střídavé cesty vzhledem k F. 

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. (a) Pokud existuje hrana e, t.ž. H', vzniklý z H odebráním
hrany e a všech jejích vrcholů, je souvislý (spec. neobsahuje
žádnou prázdnou hranu), tak tvrzení platí -- dokonce pro tuto
e lze najít vhodné f. Pokud taková hrana e neobsahuje, použijte
indukci.
(b) Indukcí -- odeberte hranu e nalezenou v části (a). 

6. (a) [ek!] = k [e(k-1)!] + 1 -- postupujte podobně jako pro R(k,l). 
(b) Horní odhad snadno z minula. Pro spodní zkuste ukázat, že 
nějaké obarvení funguje, aniž byste ho našli -- buď počítáním 
dvěma způsoby, nebo "pravděpodobnostní metodou", obarvení vybereme 
náhodně.