Witam,
oto zadanie z którym mam problem:
"Dla jakich wartości parametru n dopełnienie ścieżki \(\displaystyle{ P_{n}}\) jest grafem Hamiltonowskim? "
Z moich "luźnych" rozważań wynikło, że jest to spełnione dla \(\displaystyle{ n \ge 5}\), jednak rozwiązania nie jestem pewny(moje rozumowanie: dla \(\displaystyle{ n=2,3,4,5}\) rozpisuje ścieżki "ręcznie", dalej zauważam że stopień minimalny każdego z wierzchołków dopełnień ścieżek o \(\displaystyle{ n \ge 6}\) jest równy co najmniej \(\displaystyle{ n-3}\), więc używam tw. Diraca w następujący sposób-> \(\displaystyle{ n-3 \ge \frac{n}{2}}\) i otrzymuje rozwiązanie \(\displaystyle{ n \ge 6}\)).
Z góry dziękuję za odpowiedź oraz pozdrawiam,
Tesla