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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze