# Zkouška Kantor 29. 1. 2025
1. *[10 bodů]* Dokažte následující vztah (výpočtem nebo kombinatorickou úvahou nebo nějak jinak), pro $n \geq 1$:
$$
\sum_{k=0}^{n}k \cdot \binom{n}{k} = n \cdot 2^{n-1}
$$

2. 
    (a) *[2 body]* Doplňte definici **symetrické relace**:  
    Řekneme, že relace $R$ na množině $X$ je *symetrická*, pokud…

    (b) *[3 body]* Nechť $R$ je relace $\{(1, 1), (2, 2), (2, 3), (3, 2)\}$ na množině $X = \{1, 2, 3\}$.  
    Je $R$ **reflexivní** relace? Je $R$ **symetrická** relace? Odpovědi dostatečně zdůvodněte.

    (c) Nyní nechť $Y = \{1, 2, 3, 4\}$

    - i. *[4 body]* Kolik je všech **ekvivalencí** na množině $Y$? *(Nápověda: Ekvivalence nám dělí nosnou množinu na třídy ekvivalence.)*

    - ii. *[2 body]* Kolik je **všech relací** na množině $Y$?

    - iii. *[3 body]* Kolik je **reflexivních relací** na množině $Y$? *(Nápověda: Jak vypadá matice, která odpovídá reflexivní relaci?)*

3. *[10 bodů]* Dokažte dolní a horní mez tohoto odhadu:
$$
n^{n/2} \leq n! \leq \left( \frac{n+1}{2} \right)^n
$$

4. (a) *[4 body]* **Formulujte** *Kuratowského větu.** Stačí formulace, větu nedokazujte.

    (b) *[4 body]* Je graf na obrázku rovinný? Buďto ho nakreslete rovinně, nebo nějakým přesvědčivým (!) způsobem argumentujte, proč rovinné nakreslení neexistuje.

    (c) *[4 body]* *Průměrný stupeň grafu* $G$ je průměr jeho stupňů, neboli číslo
    $$
    \frac{1}{n} \left( \sum_{v \in V(G)}\text{deg}(v) \right)
    $$
    (kde $n$ je počet vrcholů grafu $G$). Je **pravdivé** následující tvrzení? Buďto ho dokažte (třeba s použitím nějaké věty z přednášky), nebo najděte nějaký konkrétní protipříklad.

    **Tvrzení:** *Kdykoliv $G$ je graf, který má průměrný stupeň nejvýše $2,3$, pak je $G$ rovinný.

5. (a) *[4 body]* Doplňte **definice** grafu a souvislého grafu:
    - *Graf* je…
    - Řekneme, že graf $G$ je *souvislý*, pokud…

    (b) Pokud $t$ je přirozené číslo a $t \geq 2$, tak definujeme graf $G_t$ takto: vrcholy jsou všechny **dvouprvkové množiny** čísel z množiny $\{1, \ldots, t\}$ (neboli $V(G_t) = \binom{\{1, \ldots, t\}}{2}$) a dvě takové množiny tvoří hranu právě tehdy, když jsou **disjunktní**. Zde je například obrázek $G_5$:

    (Mimochodem, tyto grafy jsou celkem důležité a mají název: Kneserovy grafy.)  
    *[4 body]* Pro každé $t \geq 2$ rozhodněte, zda je $G_t$ **souvislý** graf. Odpověď dostatečně zdůvodněte.

    (c) *[3 body]* Graf $G_t$ definovaný výše má všechny vrcholy stejného stupně. **Jakého?** (Bude to pochopitelně nějaké číslo, které závisí na $t$.) Odpověď dostatečně zdůvodněte.

    (d) *[3 body]* Nyní předpokládejme, že $t = 4k+3$ pro nějaké přirozené číslo $k$. Je graf $G_t$ (definovaný výše) **eulerovský**? Odpověď dostatečně zdůvodněte.