1. (Graf známostí)
    Vrcholy grafu jsou jména lidí a dva vrcholy jsou spojeny hranou, pokud se $2$ lidé odpovídající vrcholům znají. Dokažte následující tvrzení:

    1. V každé skupině $n\geq 2$ lidí jsou dva, kteří znají stejný počet lidí ze skupiny.
    2. Mezi šesti lidmi vždy existují $3$ lidé, kteří se vzájemně znají a nebo $3$ lidé, kteří se vzájemně neznají.1
    3. Každá skupina lidí může být rozdělena na dvě skupiny tak, aby aspoň polovina známých člověka $X$ byla v jiné skupině než $X$, pro každého člověka $X$.
    4. Pokud každý člověk zná alespoň polovinu lidí ze skupiny, tak můžeme lidi posadit kolem kulatého stolu tak, aby každý seděl mezi lidmi, které zná.
  2. (Nakreslení grafu)
    Na Obrázku jsou $3$ domečky a $3$ studny. Vaším úkolem spojit každý domeček s každou studnou pěšinou tak, aby se pěšiny vzájemně nekřížili.

    Nezkoušejte to ale déle jak $10$ minut, raději dokažte, proč to nejde.

  3. Jaký je maximální počet vrcholů binárního stromu o $h$ hladinách? A jaký je maximální počet vrcholů $k$-árního stromu o $h$ hladinách? Co z toho plyne pro minimální výšku těchto stromů? Kolik může být maximální výška binárního stromu?
  4. Dokažte, že v binárním stromě je počet vnitřních uzlů stupně dva roven počtu listů mínus jedna.
  5. Dokažte, že v každém binárním stromě s $L$ listy existuje podstrom s $l\in \langle L/3, 2L/3 \rangle$ listy.