Wykazać, że w grafie istnieje ścieżka.

[Mathix]

Cześć,

mam proste zadanie, ale generalnie nie za bardzo czuję jak się zabierać za zadania z grafów, więc prosiłbym o jakieś wskazówki.

Zad. Jeżeli graf G jest prosty oraz najmniejszy stopień wierzchołka w grafie jest większy lub równy k (\(\displaystyle{ \delta (G) \ge k}\)) to graf ten posiada ścieżkę długości k.

[leg14]

Sciezke budujesz indukcyjnie (zaczynajac od wierzcholka o najmniejszym stopniu). Załóżmy, że wybrałeś już \(\displaystyle{ a_1,..,a_l}\) i \(\displaystyle{ l < k}\). Z założenia \(\displaystyle{ deg(a_l) \ge k}\) zatem istnieje wierzchołek \(\displaystyle{ v}\) połączone krawędzią z \(\displaystyle{ a_l}\), który nie należy do zbioru \(\displaystyle{ \left\{ a_1,..,a_l\right\}}\). Kładziemy \(\displaystyle{ a_{l+1} = v}\)