Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Dokaz

Dokaz poteka z indukcijo na število točk. Trditev očitno drži za vse grafe na dveh točkah (takšna grafa sta samo dva, $K_2$ in njegov komplement). Denimo, da trditev drži za vse grafe na manj kot $n$ točkah. Dokažimo, da tedaj velja tudi za graf $\Gamma$ na $n$ točkah.

(1) $\Rightarrow$ (2): Denimo, da je $\Gamma$ drevo. Tedaj je povezan po deficiji. Naj bo $e = uv$ poljubna povezava grafa $\Gamma$. Tedaj je $(u,v)$ edina pot med $u$ in $v$. To pa pomeni, da v grafu $\Gamma - e$ ni nobene poti, kar pomeni, da $\Gamma$ ni povezan.

(2) $\Rightarrow$ (3): Predpostavimo, da je $\Gamma$ povezan, odstranitev poljubne povezave pa ga razbije. Dokazujemo enakost $\mid E(\Gamma) \mid = \mid V(\Gamma) \mid - 1$. Izberi povezavo $e$. Tedaj je $\Gamma - e$ unija povezanih komponent $X$ in $Y$ (premisli, da sta povezani komponenti dve in ne morda tri ali več). Grafa $X$ in $Y$ sta povezana, če pa odstanimo kakšno povezavo, razpadeta (saj če ne bi razpadla, ne bi ob odstranitvi te iste povezave razpadel niti graf $\Gamma$). Uporabimo indukcijo in dobimo $\mid E(X) \mid = \mid V(X) \mid -1$ and $\mid E(Y) \mid = \mid V(Y) \mid -1$. Tedaj

$$\mid E(\Gamma)\mid = \mid E(X)\mid + \mid E(Y) \mid + 1 = (\mid V(X) \mid -1)+(\mid V(Y) \mid -1)+1 = \mid V(\Gamma) \mid-1.$$

(3) $\Rightarrow$ (4): Predpostavljamo, da je $\Gamma$ povezan in da zadošča pogoju $\mid E(\Gamma) = \mid V(\Gamma)\mid -1$. Dokazujemo, da $\Gamma$ nima ciklov. Pa recimo, da obstaja cikel $C$. Za vsak $v \in V(\Gamma)$ poiščemo prvo povezavo $e_v$ na kaki najkrajši poti med $v$ in $C$. Premislek pokaže, da je $e_v \ne e_u$ za poljubni različni točki $u,v \in V(\Gamma) \setminus V(C)$. Zato je

$$\mid E(\Gamma) \ge \mid E(C) \mid \cup \mid \{e_v :v \in V(\Gamma) \setminus V(C)\} \mid = V(\Gamma),$$

kar je protislovje.

(4) $\Rightarrow$ (5): Predpostavljamo, da je $\Gamma$ brez ciklov in da velja $\mid E(\Gamma) \mid = \mid V(\Gamma) \mid - 1$. Dokazati moramo, da je $\Gamma$ povezan. Naj bodo $X_1,...,X_k$ komponente za povezanost in denimo, da je $k \ge 2$. Vsak izmed grafov $X_i$ zadošča (5), zato po indukcijski predpostavki $X_i$ zadošča tudi (4). Tedaj pa je $\mid E(X_i) \mid = \mid V(X_i) \mid - 1$. Po drugi strani:

$$\mid E(\Gamma) \mid = \sum^k_{i=1} \mid E(X_i) \mid = \sum^k_{i=1} \mid V(X_i) \mid - k.$$

Ker je $\mid E(\Gamma) \mid = \mid V(\Gamma) \mid - 1$, sledi $k = 1$, in $\Gamma$ je povezan.

(5) $\Rightarrow$ (1): Predpostavljamo, da je $\Gamma$ povezan in brez ciklov. Dokazujemo, da obstaja med poljubnima točkama natanko ena pot. Zaradi povezanosti obstaja vsaj ena pot. Če bi bili dve, bi dobili cikel – protislovje.

Dokaz

Naj bo $\Gamma$ graf, v katerem ima vsaj $\mid V(\Gamma) \mid - 1$ točk stopnjo vsaj $2$ (označimo množico teh točk z $U$). Preostala točka ima stopnjo vsaj $1$, saj bi sicer tvorila komponentno za povezanost. Tedaj je

$$\mid E(\Gamma) \mid = \frac{1}{2}(\sum_{v \in U} deg(v) + 1) \ge \frac{1}{2}(\mid V(\Gamma) \mid \cdot 2+1) = \mid V(\Gamma) \mid + \frac{1}{2}.$$

Pri tem smo pri prvi neenakosti uporabili lemo o rokovanju. Sedaj pa iz trditve 9.1 sledi, da $\Gamma$ ni drevo, kar je protislovje

Dokaz

Če graf $\Gamma$ vsebuje vpeto drevo, obstaja pot med poljubnima dvema točkama že v drevesu. Zato je $\Gamma$ povezan. Naj bo sedaj $\Gamma$ povezan graf. Če je $\Gamma$ drevo, je trditev dokazana. Sicer obstaja povezava $e$, za katero je $\Gamma - e$ povezan. Odstranimo $e$ iz $\Gamma$ in postopek nadaljujemo, dokler ne dobimo (vpetega) drevesa.

Dokaz

Vpetih dreves multigrafa $\Gamma$, ki povezave $e$ ne vsebujejo, je natanko toliko kot vpetih dreves multigrafa $\Gamma - e$. Po drugi strani pa iz vpetega drevesa multigrafa $\Gamma$, ki vsebuje povezavo $e$, s skrčitvijo te povezave dobimo vpeto drevo multigrafa $\Gamma/e$. Ta postopek nam očitno da bijekcijo med vpetimi drevesi multigrafa $\Gamma$, ki vsebujejo povezavoe, z vpetimi drevesi multigrafa $\Gamma/e$.