Drzewa - stopnie

[ucaps]

Witam,
treść mojego zadania przedstawia się następująco.

Niech \(\displaystyle{ k > 1}\) będzie liczbą naturalną. Wykaż, że każde niepuste \(\displaystyle{ n}\)-wierzchołkowe drzewo posiada co najmniej \(\displaystyle{ n - \frac{n-2}{k-1}}\) wierzchołków stopnia mniejszego niż \(\displaystyle{ k.}\)

Jakieś wskazówki co do rozwiązania tego zadania?
Pozdrawiam.

[Mruczek]

Załóżmy nie wprost, że graf ma mniej niż \(\displaystyle{ n - \frac{n-2}{k-1}}\) wierzchołków stopnia mniejszego niż \(\displaystyle{ k}\). To znaczy, że ten graf ma więcej niż \(\displaystyle{ \frac{n - 2}{k - 1}}\) wierzchołków stopnia nie mniejszego niż \(\displaystyle{ k}\).
Załóżmy, że ma \(\displaystyle{ \frac{n - 2}{k - 1} + a}\) wierzchołków stopnia nie mniejszego niż \(\displaystyle{ k}\), gdzie \(\displaystyle{ a > 0}\). Pozostałe \(\displaystyle{ n - \frac{n - 2}{k - 1} - a}\) wierzchołków ma stopień mniejszy niż \(\displaystyle{ k}\), ale równy co najmniej \(\displaystyle{ 1}\).
Drzewo o \(\displaystyle{ n}\) wierzchołkach ma \(\displaystyle{ n - 1}\) krawędzi, czyli suma stopni wierzchołków to \(\displaystyle{ 2n - 2}\). Policzmy sumę stopni wierzchołków tego drzewa - jest ona nie mniejsza niż:
\(\displaystyle{ \left( \frac{n - 2}{k - 1} + a \right) \cdot k + \left( n - \frac{n - 2}{k - 1} - a\right) \cdot 1 = 2n - 2 + ak - a}\)
\(\displaystyle{ 2n - 2 \ge 2n - 2 + ak - a}\)
\(\displaystyle{ a(k - 1) \le 0}\)
\(\displaystyle{ k > 1}\), czyli \(\displaystyle{ a \le 0}\), sprzeczność, cnd.

[ucaps]

Dzięki wielkie! Dedukcja jak najbardziej w porządku, wyhaczyłem tylko jeden błąd. W wyrażeniu:
\(\displaystyle{ \left( \frac{n - 2}{k - 1} + a \right) \cdot k + n - \left( \frac{n - 2}{k - 1} - a\right) \cdot 1 = 2n - 2 + ak - a}\)

Powinno być \(\displaystyle{ n - \left( \frac{n - 2}{k - 1} + a\right)}\) zamiast \(\displaystyle{ n - \left( \frac{n - 2}{k - 1} - a\right)}\)

Zimne piwko dla Ciebie!
Pozdrawiam