# Kombagra II

<{ForumPost(poster="Oracions", timestamp=2014-02-05 17:37:24)}>
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").
<{/ForumPost}>

<{ForumPost(poster="Tajpan", timestamp=2014-07-10 18:59:30)}>
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
<{/ForumPost}>