Nastavení

Větu převedeme na ekvivalentní tvrzení: Mějme nejdelší cestu $P$ ve stromu $T$ s krajními vrcholy $u$ a $v$. Vrcholy $u$ a $v$ musí být listy.

Tuto větu dokážeme sporem. Snažíme se tedy vyvrátit tvrzení, že máme nejdelší cestu $P$ v $T$ ale $u$ nebo $v$ nejsou listy.

Řekněme že $v$ není list. (Analogicky bychom dokázali pro případ kdy $u$ není listem)

Pokud $v$ není list, pak z něj musí vést alespoň 2 hrany. Jedna musí nutně patřit do cesty $P$.

Druhá hrana ale nepatří do naší cesty, jelikož $v$ je koncový vrchol. Označme si tuto hranu $e = \{v, w\}$.

• Pokud $v \in V(P)$, pak by v $T$ byla kružnice, což je ve sporu s předpokladem že $T$ je strom.

• Pokud $v \notin V(P)$, pak by šla cesta $P$ prodloužit a tím pádem by už nebyla nejdelší, což je ve sporu s předpokladem, že $P$ je nejdelší cesta v $T$.

$\square$

1. Nechť $P$ je nejdelší cesta ve stromu $T$

2. Nechť $u$ a $v$ jsou její koncové vrcholy

3. Sporem ukážeme, že $u$ a $v$ jsou listy

4. Kdyby z $u$ vedly aspoň dvě hrany, jedna z nich bude patřit do $u\text{-}v\text{-cesty }P$ a zbývat bude ještě aspoň jedna hrana $e = \{u,v\}$

5. Kdyby $w \in V(P)$, byla by v $T$ kružnice (SPOR)

6. Kdyby $w \notin V(P)$, cesta $P$ by šla prodloužit a nebyla by tedy nejdelší (SPOR)

7. To samé platí pro koncový vrchol $v$

Protože cesty jsou stromy, existují stromy mající pravě 2 listy

$\square$

Nechť $G = (V, E)$ je graf na aspoň 2 vrcholech a nechť $v \in V$ je jeho list.

1. $G - v$ je souvislý:

   • Zvolme dva libovolné $x, y \in V \setminus \{v\}$ a cestu $P$ mezi nimi (ta existuje, protože $G$ je souvislý).

   • $P$ nemůže obsahovat $v$, jelikož $v$ je stupně 1 a jediné jiné vrcholy stupně 1 v $P$ jsou $x$ a $y$ které ale z předpokladu nemohou být $v$.

   • Tím jsme dokázali, že mezi každými $x, y \in V \setminus \{v\}$ musí vést cesta, která neobsahuje vrchol $v$ a tím pádem odstranením $v$ z $G$ cestu nepřerušíme.

   • Tím jsme tedy dokázali, že $G - v$ je souvislý.

2. $G - v$ je bez kružnic:

   • $G$ je strom, tedy je acyklický. $G - v$ je podgraf $G$ a proto je také acyklický.

Tedy $G - v$ je strom.

$\square$

1. $G$ je souvislý:

   • Ze souvislosti $G - v$ plyne, že mezi každými dvěma $x, y \in V \setminus \{v\}$ vede cesta v $G - v$

   • Cesta v $G$ z libovolného vrcholu $x$ do $v$ vznikne prodloužením cesty mezi $x$ a $w$ do vrcholu $v$, kde $w$ je (jediný) soused listu $v$

2. $G$ je bez kružnic:

   • Vrácením listu $v$ do grafu $G$ (přidáním listu ke stromu $G - v$) nevytvoříme kružnici (do $v$ povede jen jedna hrana)

Tedy $G$ je strom.

$\square$

1. Strom je souvislý, proto $\forall x,y \in V$ $\exists$ $u\text{-}v\text{-cesta}$

2. Pro spor předpokládejme, že existují dva vrcholy $u$ a $v$, mezi kterými existují aspoň dvě různé cesty $P_1 = a_1, ..., a_k$ a $P_2 = b_1, ..., b_l$ (tedy $a_1 = b_1 = u$ a $a_k = b_l = v$)

3. Nechť $i \ge 1$ je nejmenší index takový, že $a_i = b_i$ a $a_{i+1} \ne b_{i+1}$

4. Označme $p,q > i$ takovou dvojici indexů, že $a_p = b_q$ a $\{ a_{i+1}, ..., a_{p-1} \} \cap \{ b_{i+1}, ..., b_{q-+} \} = \emptyset$

5. Pak ale vrcholy $\{ a_i, a_{i+1}, ..., a_{p-1}, a_p \}$ a $\{ b_{i+1}, ..., b_{q-1} \}$ dohromady tvoří v $G$ kružnici - spor s předpokladem $G$ je strom

$\square$

1. Z předpokladu vyplýva, že $G$ je souvislý

2. Pokud by v $G$ byla kružnice, tak by mezi nějakými dvěma jejími vrcholy existovaly alespoň dvě různé cesty, což je spor s předpokladem

3. $G$ je tedy strom

$\square$

1. Souvislost je splněna triviálně ($G$ je strom)

2. Předpokládejme pro spor, že existuje hrana $e = \{u, v\} \in E$ taková, že graf $G - e = (V, E \setminus \{e\})$ je souvislý

3. Pak v $G - e$ musí existovat $u\text{-}v\text{-cesta}$, která se ale po přidání hrany $e$ stane v grafu $G$ kružnicí, což je spor s předpokladem, že $G$ je strom

$\square$

1. Souvislost je splněna, stačí ukázat neexistunci kružnic v $G$

2. Předpokládejme pro spor, že současně platí:

   1. Vynecháním libovolné hrany v $G$ vznikne nesouvislý graf

   2. $G$ obsahuje kružnici $C$

3. Vyjmeme-li z $G$ ale libovolnou hranu $e = \{x, y\} \in C$, pak se $G$ nerozpadne na dvě komponenty, protože jakékoliv cestě mezi libovolnými 2 vrcholy $u$ a $v$, která před tím obsahovala $e$ poskytne $C$ alternativní spojení.

4. Pro hrany kružnice $C$ tudíž předpoklad 2.1 neplatí - dostali jsme spor

$\square$

1. Souvislost je splněna triviálně

2. Pro důkaz $|V| = |E| + 1$ použijeme indukci podle $|V|$

3. Pro $|V| = 1$ tvrzení platí triviálně.

4. Předpokládejme tedy $|V| > 1$

5. Dle Věty o existenci listů existuje ve stromu $G$ list $v$

6. Graf $G - v$ je dle Věty o trhání listů opět strom

7. Dle indukčního předpokladu tedy platí $|V(G - v)| = |E(G - v)| + 1$

8. Vrátíme-li list $v$ do grafu $G$, zvyšíme počet vrcholů i počet hran o jedna. Proto $|V| = |V(G - v)| + 1 = (|E(G - v)| + 1) + 1 = |E| + 1$

$\square$

1. Indukcí podle $|V|$. Pro $|V| = 1$ platí tvrzení triviálně

2. Ukážeme nejdříve, že z předpokladu plyne, že v $G$ existuje list

   1. Dle předpokladu platí $\sum_{u \in V} \text{deg}_G (u) = 2|E| = 2|V| - 2$

   2. Kdyby pak všechny stupně v $G$ byly aspoň 2 pak $\sum_{u \in V} \text{deg}_G (u) > 2|V|$

   3. Tedy nějaký vrchol musí mít stupeň menší než 2. Označme ho $v$.

   4. Protože $G$ je souvislý, vrchol $v$ nemůže mít stupeň 0.

   5. Tím pádem musí mít $v$ stupeň 1 a proto vrchol $v$ je list.

3. Graf $G - v$ je souvislý a splňuje $|V(G - v)| = |E(G - v)| + 1$, neboť jsme z $G$ odebrali 1 vrchol a 1 hranu

4. $G - v$ je tedy dle indukčního předpokladu strom

5. Dle Věty o trhání listů je tedy $G$ také strom

$\square$