Ile jest wszystkich drzew rozpiętych na n wierzchołkach...

[PanTy]

Witam,
Potrzebuje pomocy z zadaniem z teorii grafów. Nie mam pojęcia jak je rozwiązać i będę niesamowicie wdzięczny za pomoc i wyjaśnienie.

Treść:

Ile jest wszystkich drzew rozpiętych na zbiorze wierzchołków \(\displaystyle{ \{1,2,3,...n\}}\), \(\displaystyle{ n > 12}\) w których wierzchołek \(\displaystyle{ 1}\) ma stopień \(\displaystyle{ 12}\), a wierzchołek \(\displaystyle{ 2}\) ma stopień \(\displaystyle{ n-12}\)? Odpowiedź należy wyczerpująco uzasadnić.

Z góry dziękuję.

Pozdrawiam.

[mostostalek]

Należy zadać sobie pytanie.. Czy może istnieć drzewo o takich własnościach, w którym nie istnieje krawędź pomiędzy wierzchołkiem \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\).. Otóż zauważyć należy, że jeśli istnieje krawędź między tymi wierzchołkami i do wierzchołka \(\displaystyle{ 1}\) przyłączymy jeszcze 11 innych wierzchołków to pozostanie nam \(\displaystyle{ n-13}\) wierzchołków do dyspozycji.. Zauważmy, że wierzchołek \(\displaystyle{ 2}\) ma w tej chwili stopień 1 ponieważ nie może istnieć żadna krawędź między nim a którymś z 11 wierzchołków przyłączonych do wierzchołka \(\displaystyle{ 1}\)(powstałby cykl).. Wszystkie pozostałe wierzchołki, należy przyłączyć zatem do wierzchołka \(\displaystyle{ 2}\), aby spełnić założenie o stopniu tegoż wierzchołka..
Czy może istnieć drzewo o takich własnościach bez krawędzi \(\displaystyle{ (1,2)}\)? Otóż jeśli do \(\displaystyle{ 1}\) przyłączymy 12 wierzchołków i nie będzie wśród nich \(\displaystyle{ 2}\) to oprócz \(\displaystyle{ 2}\) pozostanie nam jeszcze \(\displaystyle{ n-14}\) wierzchołków.. Jeśli przyłączymy \(\displaystyle{ 2}\) do któregoś z wierzchołków przyłączonych do \(\displaystyle{ 1}\) to i tak zabraknie nam wierzchołków na spełnienie założenia odnośnie stopnia wierzchołka \(\displaystyle{ 2}\)
Odpowiedź zatem brzmi: Nie istnieje drzewo rozpięte na \(\displaystyle{ n}\) wierzchołkach w którym wierzchołek \(\displaystyle{ 1}\) ma stopień \(\displaystyle{ 12}\), wierzchołek \(\displaystyle{ 2}\) ma stopień \(\displaystyle{ n-12}\) i nie istnieje krawędź między wierzchołkami \(\displaystyle{ 1}\) i \(\displaystyle{ 2}\).
Zauważmy również, że nie może być również krawędzi między żadnymi dwoma z dwunastu wierzchołków przyłączonych do \(\displaystyle{ 1}\)(powstałby cykl), ani krawędzi między żadnymi dwoma wierzchołkami przyłączonymi do \(\displaystyle{ 2}\).
Zauważmy zatem, że wybór tych 11 wierzchołków przyłączonych do \(\displaystyle{ 1}\) utworzy nam cały graf..
Drzew o zadanych własnościach jest zatem \(\displaystyle{ {n \choose 11}}\)