Důkaz:

Nechť vrcholy v0,v1,v2,...,vk jsou vrcholy nějaké nejdelší cesty P v T. Délka cesty P je k. (Využíváme předpoklad, že T je konečný graf.) Pak tvrdíme, že degTv0=degTvk=1, v opačném případě by existovala:

• hrana {vi,vs}, i∈{0,k}, vs∈P, s∈{1,2,...,k-1}, což by vedlo k existenci kružnice, a to by byl spor s tím, že T je strom
• hrana {vi,vs}, i∈{0,k}, vs∉P, což by vedlo k existenci cesty P´=P∪{vi,vs} délky k+1, a to by byl spor s nejdelší cestou P
• degTvi=0, i∈{0,k}, pak T obsahuje izolovaný vrchol a není souvislý, což je spor s tím, že T je strom.

V každém případě dojdeme ke sporu, proto degTv0=degTvk=1.∎

Důkaz (E.Milková:Problém minimální kostry):

Zřejmě graf T'=T-v neobsahuje kružnici. Zbývá dokázat, že graf T' je souvislý graf. Nechť x,y jsou dva libovolné vrcholy stromu T různé od vrcholu v a nechť Px,y je cesta z vrcholu x do vrcholu y ve stromu T. Cesta Px,y neobsahuje vrchol v, neboť cesta může obsahovat nejvýše dva vrcholy stupně jedna (koncové vrcholy cesty) a těmi by mohly být pouze vrcholy x a y. Cesta Px,y je tak celá obsažena i v grafu T' a graf T' je tudíž souvislý.

Postupným odtrháváním listů dostáváme z původního stromu stále menší a menší stromy, až nakonec obdržíme triviální strom.∎

Důkaz (E.Milková:Problém minimální kostry):

Přidáním jednoho vrcholu a jedné hrany ke grafu nemůžeme zřejmě kružnici vytvořit. Zbývá dokázat, že graf T'=(V∪{w}, E∪{v,w}) získaný ze stromu T přidáním hrany {v,w}, v∈V, w∈V, bude souvislý. To však zřejmě plyne ze skutečnosti, že pro každé dva vrcholy x a y grafu T' různé od vrcholu w existuje cesta z x do y v grafu T' totožná s cestou z x do y ve stromu T. A cestu v grafu T' z libovolného vrcholu x do vrcholu w dostaneme prodloužením cesty z vrcholu x do vrcholu v ve stromu T o hranu {v,w}. A naopak cestu z vrcholu w do libovolného vrcholu x v grafu T' získáme připojením cesty z vrcholu v do vrcholu x ve stromu T k hraně {w,v}.

Vrchol w je zřejmě stupně 1, list nově vytvořeného stromu.∎

Důkaz:

Dukaz sporem: ∃G =(V,E): G je strom, a zároveň existuje alespoň jedna hrana, která není most.

Existuje alespoň jedna hrana, která není most. Označme hranu e=(x,y) ⇒(definice mostu)⇒ G-e má stejný počet komponent jako G (komponenta, která obsahuje e je po odebrání hrany e opět souvislá) ⇒(definice souvislosti)⇒ v G-e existuje cesta mezi vrcholy x a y, označme ji Pxy, pak e∪Pxy je kružnice v G a dostáváme spor s tím, že G je strom (strom je graf souvislý bez kružnic). Negace neplatí, platí původní tvrzení.∎

Důkaz:

vykonáme postupným ověřováním implikací: (1)⇔(2), (1)⇔(3), (1)⇔(4), (1)⇔(5), (1)⇔(6)

• (1)⇒(2) - T je strom ⇒ ∀x,y∈V ∃!Px,y(∼ mezi libovolnými dvěma vrcholy grafu T existuje právě jedna cesta).

  Pro důkaz sporem předpokládejme, že platí: T je strom a zároveň existuje dvojice vrcholů mezi kterými buď cesta neexistuje, což však je spor s předpokladem, že strom je souvislý graf nebo mezi nimi existuje více cest, viz obrázek, což však je spor s předpokladem, že strom je graf bez kružnic.

  

• (2)⇒(1) - ∀x,y∈V ∃!Px,y ⇒ T je strom

  Z předpokladu ihned plyne, že T je souvislý graf.

  Pro důkaz druhé vlastnosti stromu, tedy toho, že v T neexistuje kružnice, budeme pro spor předpokládat, že platí: ∀x,y∈V ∃!Px,y a zároveň v grafu T alespoň jedna kružnice existuje. Označme C=(v0,e1,v1,...,vk-1,ek,v0) kružnici v T. Pak ale posloupnost (v0,e1,v1) a posloupnost (v0,ek,vk-1,...,v1) tvoří dvě cesty z vrcholu v0 do vrcholu v1, což je spor s předpokladem, že mezi každou dvojicí vrcholů, tedy i mezi v0 a v1, existuje právě jedna cesta.

• (1)⇒(3) - T je strom ⇒ T je souvislý a platí vztah m=n-1

  Souvislost grafu T plyne přímo z předpokladu (T je strom).

  Platnost vztahu m=n-1 dokážeme MI (podle počtu vrcholů):

  1. Pro strom s 1 vrcholem (= triviální strom) platí: n=1, m=0 ... 0=1-1...vztah platí

     Pro strom s 2 vrcholy (= 1 hrana) platí: n=2, m=1 ... 1=2-1...vztah platí

  2. IP: Předpokládejme, že tvrzení je pravdivé pro stromy s méně než n vrcholy. Uvažujme nějakou hranu e={u,v}∈E(T). Tato hrana, podle předpokladu, tvoří jedinou cestu mezi vrcholy u a v, jinak by v stromu existovala kružnice. Teda v T-e není žádna cesta mezi u a v. Graf T má právě dvě komponenty, nechť jsou to T1 a T2. Nechť n1,m1 je počet vrcholů a hran v T1 a n2,m2 je počet vrcholů, hrán v T2. Pak máme:

     n=n1+n2

     m=m1+m2+1

     Protože n1<n∧n2<n, podle indukčního předpokladu máme:

     m1=n1-1∧m2=n2-1

     Pak m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1

• (3)⇒(1) - T je souvislý a platí vztah m=n-1 ⇒ T je strom

  T je souvislý. K tomu, aby byl T strom, potřebujeme ještě dokázat, že T neobsahuje kružnici.

  Uděláme to sporem. Označme T0=T. A předpokládejme, že T0 obsahuje kružnici. Nechť T1=T0-e1, kde e1 je kružnicová hrana. Z předpokladu máme, že T0 je souvislý a podle tvrzení: Nechť graf G je souvislý a nechť obsahuje kružnici C. Pak graf G-e, kde e je libovolná hrana kružnice C, je také souvislý, je také T1 souvislý, T1 má n vrcholů a m-1 hran.

  Když T1 obsahuje kružnici a e2 je kružnicová hrana. Pak T2=T1-e2 je opět souvislý graf a má n vrcholů a m-2 hran. Tento postup opakujeme, až dokud nedostaneme graf Tp, který neobsahuje kružnici, je souvislý a má n vrcholů a m-p hran. Podle definice je Tp strom a podle předchozího tvrzení (1)⇒(3) platí: počet hran se rovná počet vrcholů mínus 1.

  > m-p=n-1

  Pro spor jsme předpokládali existenci kružnice, což znamená p≥1. Ale to se dostáváme do sporu s předpokladem, že m=n-1. Proto musí platit p=0, což znamená, že T neobsahuje kružnici. A podle definice je T strom.

• (1)⇒(4) - T je strom ⇒ T je souvislý a každá jeho hrana je most

  Souvislost grafu T plyne přímo z předpokladu (T je strom).

  Pro důkaz druhé části tvrzení, tedy toho, že každá hrana T je most, předpokládejme pro spor, že graf T je strom a zároveň v T existuje hrana e={v,w}, která není mostem. Jestliže hrana e není mostem, je zřejmé (viz definice mostu), že i graf T=e je souvislý a tudíž v něm existuje mezi vrcholy v,w cesta P. Cesta P je cestou mezi vrcholy v,w i v grafu T a spolu s hranou e tvoří v T kružnici, což je spor s předpokladem, že T je strom.

• (4)⇒(1) - T je souvislý a každá jeho hrana je most ⇒ T je strom.

  K důkazu toho, že souvislý graf T, jehož každá hrana je most, je strom, potřebujeme pouze ukázat, že v grafu T neexistuje kružnice. Pro spor předpokládejme, že v T kružnice existuje. Pak ale vyjmutím libovolné hrany e ležící na této kružnici dostáváme dle tvrzení (Nechť graf G je souvislý a nechť obsahuje kružnici C. Pak graf G-e, kde e je libovolná hrana kružnice C, je také souvislý.) opět souvislý graf, což je spor s předpokladem, že hrana e je most.

• (1)⇒(5) - T je strom ⇒ T neobsahuje kružnici a m=n-1

  T neobsahuje kružnici plyne z definice stromu: strom je souvislý a neobsahuje kružnice.

  Vztah m=n-1 dokážeme MI (podle počtu vrcholu)

  1. n=1 ⇒ T je triviální strom ⇒ m=0∧0=1-1 ... platí

     n=2 ⇒ T je hrana ⇒ m=1∧1=2-1 ... platí

  2. Předpokládejme, že tvrzení je pravdivé pro stromy s méně než n vrcholů. Uvažujme nějakou hranu e={u,v}∈E(T). Tato hrana, podle předpokladu, tvoří jedinou cestu mezi vrcholy u a v, jinak by v stromu existovala kružnice. Teda v T-e není žádna cesta mezi u a v. Graf T má právě dvě komponenty, nechť jsou to T1 a T2. Nechť n1,m1 je počet vrcholů, hrán v T1 a n2,m2 je počet vrcholů, hrán v T2. Pak máme

     n=n1+n2

     m=m1+m2+1.

     Protože n1<n∧n2<n, podle indukčního předpokladu máme:

     m1=n1-1∧m2=n2-1

     Teda m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=nspan>-1.

• (5)⇒(1) - T neobsahuje kružnici a m=n-1 ⇒ je strom

  K důkazu, že T je strom, ještě potřebujeme dokázat souvislost. Sporem:

  Nechť T není souvislý a T1,T2,...,Tp je p komponent grafu T s ni vrcholy a mi hranami v Ti, pro i=1,...,p. Potom m=m1+m2+...+mp a n=n1+n2+...+np.

  Každá komponenta Ti je bez kružnic (podle předpokladu), tedy je strom. Podle (3) máme mi=ni-1 pro všechny 1≤i≤p. Pak dostáváme

  $$m=\sum _{i=1}^p{m}_i=\sum _{i=1}^p(n_i-1)=n-p$$

  Dostáváme spor s předpokladem, že m=n-1, proto musí platit p=1. Tedy T má jedinou komponentu, tj. je souvislý. Protože T je souvislý a je bez kružnic, podle definice stromu, je T strom.

• (1)⇒(6) - T je strom ⇒ T neobsahuje kružnici a každý graf vniklý z grafu T přidáním hrany, která spojuje libovolné dva vrcholy grafu T, které nejsou sousední, již kružnici obsahuje

  Neexistence kružnice v grafu T plyne přímo z předpokladu (T je strom). Nechť x,y jsou dva libovolné vrcholy stromu T, které nejsou sousední. Ze souvislosti stromu T víme, že z vrcholu y do vrcholu x existuje cesta, označme ji P. Přidáním hrany {x,y} ke stromu T dostáváme graf, který již kružnici obsahuje, kružnici (x,y,P).

• (6)⇒(1) - T neobsahuje kružnici a každý graf vniklý z grafu T přidáním hrany, která spojuje libovolné dva vrcholy grafu T, které nejsou sousední, již kružnici obsahuje ⇒ T je strom

  K důkazu toho, že graf T je strom, potřebujeme pouze dokázat, že graf T je souvislý. Uvažujme pro spor, že kdyby graf T nebyl souvislý, existovaly by v něm alespoň dvě komponenty, označme je K1 a K2. Přidáním libovolné hrany {x,y}, kde x∈K1 a y∈K2, ke grafu T by nevznikl graf obsahující kružnici, neboť hrana {x,y} by byla zřejmě most. Ale to by byl spor s předpokladem.∎

Důkaz (E.Milková:Problém minimální kostry):

Označme Ti=(Vi,Ei), i=1,2,...,k, komponenty lesa G. Protože každá komponenta je strom, platí |Vi|=|Ei|+1, i=1,2,...,k. Odtud: