Cykl w grafie

[jolka258]

Niech \(\displaystyle{ G}\) będzie grafem zawierającym cykl \(\displaystyle{ C}\) oraz załóżmy, że \(\displaystyle{ G}\) zawiera ścieżkę (drogę) długości co najmniej \(\displaystyle{ k}\) pomiędzy dwoma dowolnymi wierzchołkami z cyklu \(\displaystyle{ C}\). Pokazać, że \(\displaystyle{ G}\) zawiera cykl długości co najmniej \(\displaystyle{ \sqrt{k}}\).



Z góry dziękuje za pomoc

[Mruczek]

Rozwiążę wersję, w której wierzchołki na ścieżce nie mogą się powtarzać (ta ścieżka to ścieżka prosta). W takiej wersji to zadanie znajduje się w książce Diestel, Graph Theory.

Hint:    

Rozważ jakąś ścieżkę o początku i końcu na tym cyklu i popatrz na jakie kawałki zostaje ona podzielona przez ten cykl.

Rozwiązanie:    

Weźmy pewną z takich ścieżek długości \(\displaystyle{ k}\) o początku i końcu na cyklu \(\displaystyle{ C}\). Jeżeli ma ona wspólnych co najmniej \(\displaystyle{ \sqrt{k}}\) wierzchołków z cyklem \(\displaystyle{ C}\) to oczywiście ma on długość co najmniej \(\displaystyle{ \sqrt{k}}\) i jest szukanym cyklem. Jeżeli nie, to zaznaczmy na tej ścieżce wierzchołki wspólne z cyklem \(\displaystyle{ C}\) - jest ich co najwyżej \(\displaystyle{ \sqrt{k}}\), więc dzielą one tą ścieżkę na co najwyżej \(\displaystyle{ \sqrt{k}}\) części, które w sumie mają długość \(\displaystyle{ k}\) - z zasady szufladkowej Dirichleta, któraś z tych części musi mieć długość co najmniej \(\displaystyle{ \sqrt{k}}\) - bierzemy tą "dobrą" część ścieżki i uzupełniamy ją do cyklu ścieżką zawartą w cyklu C o początku i końcu w końcach "dobrej" ścieżki otrzymując nowy cykl długości min. \(\displaystyle{ \sqrt{k}}\).