Matematyka.pl

Dany jest graf o \(\displaystyle{ n}\) wierzchołkach i \(\displaystyle{ k }\) krawędziach numerowanych różnymi liczbami całkowitymi od \(\displaystyle{ 1}\) do \(\displaystyle{ k}\). Udowodnić, że istnieje w nim ścieżka składająca się z co najmniej \(\displaystyle{ \frac{2k}{n}}\) krawędzi, których numery są ciągiem rosnącym.

Nazwijmy: \(\displaystyle{ \left[ \frac{2k}{n} \right] }\) - indeksem grafu czyli minimalnym ciągiem rosnącym etykiet, wziąłem część całkowitą ponieważ często wychodzą ułamki...

łatwo zauważyć, że ścieżka zamknięta ma indeks \(\displaystyle{ 2}\), a otwarta \(\displaystyle{ 1}\)...

Po zbadaniu kliki stopnia trzy wychodzi, że jej indeks wynosi dwa a kliki stopnia cztery wynosi trzy i zaryzykowałem stwierdzenie, że dla kliki stopnia \(\displaystyle{ n+1}\) jest ścieżka stopnia \(\displaystyle{ n}\)

Co łatwo udowodnić, bo przy założeniu indukcyjnym, że dla kliki stopnia \(\displaystyle{ n}\) istnieje ścieżka stopnia \(\displaystyle{ n-1}\). jeżeli teraz mamy klikę stopnia \(\displaystyle{ n+1}\) to w tej klice na pewno istnieje klika stopnia \(\displaystyle{ n}\) z indeksem \(\displaystyle{ n-1}\), więc idąc po numerach krawędzi tej kliki:

\(\displaystyle{ x_{1}<x_{2}<...<x_{n-1}<r}\) bo na pewno istnieje krawędź z wierzchołka \(\displaystyle{ n+1}\) indeksowany \(\displaystyle{ r}\) większy od jakiegokolwiek indeksu kliki \(\displaystyle{ (n)}\)...

To się samo rzuca w oczy...

Jednak nie musimy używać kliki można uogólnić do dowolnego grafu o liczbie wierzchołków \(\displaystyle{ n}\), załóżmy , że jego liczba indeksowa
wyniesie \(\displaystyle{ e= \left[ \frac{2k}{n}\right] }\). Wiadomo, że istnieje w nim ścieżka o długości \(\displaystyle{ e}\)... o rosnącym numerowaniu

Teraz jeżeli weźmiemy graf o \(\displaystyle{ n+1}\) wierzchołkach, i ten en plus pierwszy wierzchołek będzie stopnia \(\displaystyle{ n}\) to znowu znajdziemy
w nim ścieżkę o długości \(\displaystyle{ e+1}\) (indeksowaną rosnąco)...

Z: \(\displaystyle{ \frac{2\left( x_{1}+x_{2}+...+x_{n}\right) }{n} =e}\)

T: \(\displaystyle{ \frac{2\left( x_{1}+x_{2}+...+x_{n}\right)+2n }{n} =s=e+1}\)

Teraz widać, że:

\(\displaystyle{ e+1 \le (e+2) \frac{n}{n+1} <e+2}\)

Co sugeruje, że jeżeli dołożymy wierzchołek stopnia n to ścieżka (rosnąca) będzie długości \(\displaystyle{ e+1}\)