Graf spójny - minimalna ilość krawędzi

[pingwindyktator]

Mamy graf nieskierowany spójny o \(\displaystyle{ n}\) wierzchołkach. Ma on co najmniej \(\displaystyle{ n-1}\) krawędzi ( \(\displaystyle{ \Leftarrow}\) spójność). Jak to udowodnić? Indukcja po ilości wierzchołków chyba nie wchodzi w grę (albo tak mi się wydaję), myślałem nad indukcją ze względu na ilość krawędzi (troche naokoło, ale z tego wprost wynika teza po drobnych przekształceniach).

[kicaj]

Niech graf \(\displaystyle{ G}\) będzie sójnym grafem o \(\displaystyle{ n}\) wierzchołkach: \(\displaystyle{ v_1 , v_2 , ...,v_n .}\) Niech dla każdego \(\displaystyle{ 1\leqslant i \leqslant n-1}\) zapis \(\displaystyle{ L_i :v_1 , v_{k_2 } , ..., v_{k_{j_i}} , v_i}\) oznacza drogę łączącą wierzchołek \(\displaystyle{ v_1}\) z wierzchołkiem \(\displaystyle{ v_i .}\) Wówczas odwzorowanie \(\displaystyle{ f: \bigcup_i \{L_i \} \to E}\) okreslone wzorem \(\displaystyle{ f(L_i ) =\overline{v_{k_{j_i}} , v_i}}\) jest różnowartościowe, skąd wynika teza.

[norwimaj]

myślałem nad indukcją ze względu na ilość krawędzi (troche naokoło, ale z tego wprost wynika teza po drobnych przekształceniach).

Bardzo dobry pomysł.

[pingwindyktator]

myślałem nad indukcją ze względu na ilość krawędzi (troche naokoło, ale z tego wprost wynika teza po drobnych przekształceniach).

Bardzo dobry pomysł.

Czyli mogę pokazać, że mając \(\displaystyle{ n}\) krawędzi, największy (ze względu na ilość wierzchołków) graf spójny jaki mogę na tych krawędziach zbudować ma \(\displaystyle{ n+1}\) wierzchołków, tak? To prosta indukcja.

[norwimaj]

Żeby się nie myliło, użyłbym innej litery na liczbę krawędzi. Dowodzone twierdzenie, po drobnym przeformułowaniu, brzmi: (dla każdych \(\displaystyle{ n\in\mathbb{N}_+, k\in\mathbb{N}}\)) jeśli istnieje nieskierowany graf spójny o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ k}\) krawędziach, to \(\displaystyle{ k \ge n-1.}\) W kroku indukcyjnym mamy pewien graf spójny i usuwamy z niego jedną krawędź. Wtedy albo nadal będziemy mieli graf spójny, albo dostaniemy graf o dwóch spójnych składowych. Stosujemy założenie indukcyjne dla całego grafu lub dla składowych, itd.