Ekvivalentní definice stromu
Úloha číslo: 4073
Dokažte: graf \(G\) je strom právě tehdy, když \(G\) nemá kružnice a \(|E(G)|=|V(G)|-1\).
Tvrzení dokažte bez použití věty o ekvivalentních definicích stromu, resp., pokud potřebujete některou implikaci z této věty, tak ji celou reprodukujte.
Řešení
Za definici stromu vezměme, např. že je to souvislý graf bez kružnic.
Vlastnost bez kružnic se zachovává na obou stranách.
Dopředná implikace (souvislý a bez kružnic implikuje \(|E(G)|=|V(G)|-1\)):
Indukcí podle \(|V_G|\), souvislý bez kružnic má list \(u\), pro \(G-u\) platí uvedená rovnost, ta se přidáním \(u\) neporuší.
Zpětná implikace (\(|E(G)|=|V(G)|-1\) a bez kružnic implikuje souvislost):
Pro spor předpokládejme, že \(G\) je nesouvislý bez kružnic s komponentami \(C_1,…,C_k\). Komponenty jsou souvislé bez kružnic, proto splňují předchozí implikaci. Potom \(|E(G)|=|E(C_1)|+…+|E(C_k)|=|V(C_1)|-1+…+|V(C_k)|-1= |V(G)|-k\), spor.