1) Podmínka v zadání je ekvivalentní tomu, že posloupnost $I_i$ (definovaná
v ke1) je neklesající. 

2) 
a) Využijte 2-obarvení stěn. Nebo: eulerovský tah.
b) Použijte Eulerův vzorec: buď ke spočtení počtu hran v grafu (jaké cykly mohou 
být stěny?), nebo rafinovaněji ke spočtení červeno-modrých "rohů".

3)
a,b) Uvažte nejdelší cestu. 
c) Pokud takové dva vrcholy neexistují, pak listy každé kostry indukují úplný graf.

4) 
Použijte Königovu větu, podobně jako při důkazu Hallovy věty. 

5) 
a) Vezměte maximální nezávislou množinu. b) Indukcí: odstraníme vrchol, do kterého
nevedou žádné hrany, a jeho sousedy. c) Pokud je orientovaný graf silně souvislý, tak
neexistence orientovaných lichých cyklů má vážné důsledky ... 

6)
a) Takový graf obsahuje dokonce dělení $K_4$. 
b) Použijte Kuratowského větu.
c) Jediná výjimka v a) jsou grafy jejichž každý blok je $K_4$.