# Zkouska 24.6. Valtr

<{ForumPost(poster="MJS", timestamp=2009-06-24 18:22:46)}>
**1.** Dokazte nebo vyvratte: *Necht T je strom na alespon 3 vrcholech nemajici zadny vrchol stupne 2 a necht C je kruznice prochazejici vsemi listy stromu T (a nemajici zadny dalsi vrchol). Potom pridanim hran kruznice C ke stromu T vznikne 3-souvisly graf.*  
  
   Pry to jde nejak jakkoliv ukopat.  
  
**2.** Dokazte nebo vyvratte:  
a) Ma-li G HK, potom jeho vrch. souvislost je >=2.  
b) Ma-li G dve navzajem hran. disj. HK, potom je 3-souvisly.  
c) Ma-li G vsechny stupne sude a > nez 2, potom ma HK.  
  
a) Ano, jednoduche, b) ne, staci najit protipriklad c) ne: staci napr, vzit dvakrat K4,4, coz je nesouvisle a tudiz nema HK  
  
**3.** Max. tok. na oboustranne zorientovanem K_8 s kapacitami 12.  
  
    Jasne = 84  
  
**4.** Hallova veta + dukaz.  
  
Vsechno za 6 bodu, body ? : >17 >14 >11
<{/ForumPost}>