Kombagra II

Dokažte Turánovu větu.
Dokažte Tutteovu větu.
Dokažte Kuratowského větu.
Napište uzavřenou formu exponenciální vytvořující řady, kde an = počet involucí na 1..n
Nechť H je graf. Dokažte, že existuje takové číslo c, že každý graf G, který neobsahuje H jako minor, tak má barevnost menší nebo rovnu tomu číslu c.

Věty nebyly zadány všechny jménem, ale svým popisem ("co víte o tom, jak Tutte charakterizuje grafy s perfektním párováním").

dneska jsem u Jelínka měl
a) počet (ne nutně dobrých) hranových obarvení K4 k barvami neizomorfních vůči permutaci vrcholů. -> aplikace Burnsideova lemmatu
b) postačující podmínky existence Hamiltonovské kružnice v grafu. to jsem nevěděl, vyměněno za Vizingovu větu. nějaké doplňující otázky

mezi doplňujícími otázkami bylo, jak jsou na tom s hranovou barevností úplné grafy - pro lichá n $\chi\prime(K_n) = \Delta(K_n)+1$, pro sudá $\chi\prime(K_n) = \Delta(K_n)$. důkazy jsem k tomu nevěděl, po zapsání známky (trojky, vzhledem k předvedenému výkonu jsem byl spokojený) mi Jelínek navrhl, že mi je ukáže. liché n bylo hned (každý vrchol by musel mít hrany všech barev, ale vrcholů je licho, takže se nedají spárovat), ale u postupu, jak obecně obarvit sudé n, jsme se zadrhli a asi po půlhodině Jelínek naznal, že na to nemůže přijít a že můžu jít, jestli chci.

jako přednášející i zkoušející moc fajn