# Predtermín skúška - Mareš 7.1 14.00

<{ForumPost(poster="Matúš", timestamp=2022-01-07 19:50:52)}>
1. 5 ekvivalencií o stromoch - bez dôkazu   
2. Princíp inkluze a exkluze + dôkaz  
3. Majme reláciu (a,b)R(a´,b´) na množine {1,2,3,4}^2 pre ktorú platí : a = a´ ,b = b´ alebo a < a´, b < b´  
   a) Dokážte, že sa jedna o usporiadanie  
   b) Nakreslite Hasseuv diagram  
   c) min/max/najmenší/najväčší prvok  
   d*) pre všeobecné \[n]^2 najdite minimum a maximum  
4. Pre všetky n existuje rovinný súvislý graf o aspoň n vrcholov.  
a) Ukážte, že pre veľké n platí: #(v : deg(v) < 6) < |v|/100  
b*) deg(v) =< 6  
  
* - bonus
<{/ForumPost}>

<{ForumPost(poster="Villfuk02", timestamp=2022-01-07 21:35:14)}>
4. Bych napsal spíš jako  
Pro každé n najdi rovinný graf o alespoň n vrcholech, takový, že počet vrcholů se stupněm <6 je  
a) < (počet vrcholů)/100  
b*) <= 6
<{/ForumPost}>