Matematické Fórum

Zdravím,
ačkoliv je důkaz celkem jednoduchý s matematickou indukcí si nikdy nejsem moc jistý a chtěl bych se zeptat, jestli je ten důkaz takhle korektní. Vycházel jsem ze školních přednášek akorát jsem trochu víc ukecaný, protože si potřebuju každý krok zdůvodnit jaksi podrobněji, jinak ztrácím půdu pod nohama. I tak si ale nejsem 100% jistý u obou částí důkazu druhým bodem indukce.

Definice:
Strom je souvislý graf neobsahující kružnici.
V(G) = konečná množina všech vrcholů grafu G, |V(G)| = počet prvků množiny V(G)
E(G) = konečná množina všech hran grafu G,    |E(G)| = počet prvků množiny E(G)
deg(v) = stupeň vrcholu v
list = vrchol, jehož stupeň je roven 1 (list nemá potomky)
(uvažujeme pouze neorientované grafy)

Tvrzení: G je strom právě tehdy když G je souvislý a |V(G)| = |E(G)| + 1 (neboli strom o n vrcholech má n - 1 hran)
================================================
Dokážeme nejdřív G je strom => G je souvislý a |V(G)| = |E(G)| + 1

Pro |V(G)| = 1 tvrzení platí triviálně (strom G má 1 vrchol a 0 hran) (1. krok matematické indukce)

Nechť |V(G)| > 1... víme, že v G existuje list v, jeho souseda označme u (již dříve dokázaná věta o existenci listu).
Mějme graf G' který vzniknul z grafu G odebráním listu v. Víme, že i G' je strom (již dříve dokázaná věta o trhání listů).
Dále platí, že |V(G)| = |V(G')| + 1  , |E(G)| = |E(G')| + 1 (graf G' vznikl z grafu G odejmutím listu v a hrany spojující vrcholy u a v ).

Indukční předpoklad: |V(G')| = |E(G')| + 1 (graf G' o n vrcholech, tj. graf |V(G')| = n, |E(G')| = n - 1)
Platí tvrzení |V(G)| = |E(G)| + 1 i pro graf G o n+1 vrcholech? (tj. |V(G)| = n + 1, |E(G)| = n)


|V(G)| = |V(G')| + 1               (graf G' vznikl z grafu G odejmutím listu v a hrany spojující u a v )
|V(G')| + 1 = ( |E(G')| + 1 ) + 1  ( indukční předpoklad |V(G')| = |E(G')| + 1 )
( |E(G')| + 1 ) + 1 = |E(G)| + 1   (graf G' vznikl z grafu G odejmutím listu v a hrany spojující u a v )


    => |V(G)| = |E(G)| + 1
        => pokud tvrzení platí pro V(G') = n, platí i pro V(G) = n + 1 (2. krok matematické indukce)
Nejsem si jistý, jestli to opravdu takhle pro splnění 2. bodu indukce stačí: |V(G)| = |V(G')| + 1 = |V(G')| + 1 = ( |E(G')| + 1 ) + 1 = |E(G')| + 1 ) + 1 = |E(G)| + 1.

Dokážeme druhý směr implikace indukcí podle |V(G)|... G je souvislý a |V(G)| = |E(G)| + 1  => G je strom
------------------------------------------------------------------
Pro |V(G) | = 1 tvrzení triviálně platí (1. krok matematické indukce). Souvislost grafu platí z předpokladu. Ukážeme, že v grafu G existuje list...
Platí, že součet všech stupňů vrcholů  grafu G je roven 2*|E(G)| a to je rovno 2*|V(G)| - 2 (předpoklad |V(G)| = |E(G)| + 1)
Kdyby G neobsahoval list, všechny stupně by byly aspoň 2 a tedy celkový součet stupňů by byl aspoň 2*|V(G)|.
Tedy nějaký vrchol, označme jej v, musí mít nutně stupeň právě 1 (stupeň 0 to být nemůže, protože z předpokladu je graf G souvislý). Z toho plyne, že vrchol v je list.

Nechť G' je graf vytvořený z G s odebraným listem v. Graf G' je tedy souvislý a opět platí: |V(G)| = |V(G')| + 1  , |E(G)| = |E(G')| + 1.
Z předpokladu platí pro G, že |V(G)| = |E(G)| + 1 a tedy i |V(G')| + 1 = ( |E(G')| + 1 ) + 1 nebo-li: |V(G')| = |E(G')| + 1.
Takže G' s odebraným listem v je souvislý a splňuje rovnost |V(G')| = |E(G')| + 1. Graf G' je strom (vycházíme z indukčního předpokladu |V(G)| = |E(G)| + 1).
Dle věty o trhání listů je také G strom.
    => Graf G' o n vrcholech je dle indukčního předpokladu strom a graf G o n+1 vrcholech (s přidaným listem v) je také strom (již dokázaná věta o trhání listů) (2. krok matematické indukce)

Tady ztrácím pro splnění 2. kroku indukce ještě větší půdu pod nohama... argumentuju tím, že z předpokladu vím, že G je souvislý a platí |V(G)| = |E(G)| + 1. Vím, že takovému grafu můžu odebrat list (list se tam nutně nachází) a vznikne mi souvislý graf G', pro který taky platí, že |V(G')| = |E(G')| + 1 (jestli je to mé odvozování teda správné). Pokud tohle G' splňuje musí to být strom a když grafu G' vrátím zpátky jeho odebraný list (tj. dostanu G), vím, že G musí být taky strom, protože platí věta o trhání listů, která strukturu stromu zachovává. Co se mi na tom moc nezdá je, že o grafu G přeci můžu rovnou říct, že je to strom když předpokládám, že platí |V(G)| = |E(G)| + 1 a nemusím to brát přeci oklikou ne? Co tu dělám špatně?