Liczba drzew

[Vxst]

Zliczyć ile jest drzew o zbiorze wierzchołków \(\displaystyle{ [12]={1,..,12}}\), w których wierzchołek \(\displaystyle{ 5}\) ma stopień \(\displaystyle{ 2}\).

Najpierw wylosowałbym wierzchołek nr \(\displaystyle{ 5}\), a to można zrobić na \(\displaystyle{ 12}\) sposobów, a następnie \(\displaystyle{ 2}\) wierzchołki połączone z krawędzią z wierzchołkiem nr \(\displaystyle{ 5}\) na \(\displaystyle{ 11*10}\) sposobów i teraz wydaje mi się, że powinienem skorzystać z twierdzenia Cayleya. Tylko problem jest taki, że mam \(\displaystyle{ 2}\) wierzchołki od, których mogę zacząć tworzenie dalszej części drzewa, więc pomnożenie iloczynu wcześniejszych wyrażeń przez \(\displaystyle{ (n-3)^{n-5}}\) byłoby chyba błędne?

[Gouranga]

a może podejść do tego tak:
ile jest drzew ze wszystkich wierzchołków oprócz \(\displaystyle{ 5}\), później dla każdego z nich wybieramy jedną z \(\displaystyle{ 10}\) krawędzi i dzielimy ją na dwie wstawiając na niej wierzchołek \(\displaystyle{ 5}\)? nie prościej?

[Vxst]

W jednej z książek znalazłem zadanie na udowodnienie wzoru: \(\displaystyle{ {n-2 \choose k-1}(n-1)^{n-k-1}}\) dzięki któremu możemy znaleźć liczbę drzew z przynajmniej jednym wierzchołkiem o stopniu \(\displaystyle{ k}\). O ile przykład dla \(\displaystyle{ k=2}\) wydaje mi się teraz oczywisty, to dla \(\displaystyle{ k \ge 3}\) już jakoś nie mogę tego sobie wyobrazić. Mógłbyś przedstawić ogólne wytłumaczenie, tak jak to zrobiłeś dla podstawowego przypadku?

[Gouranga]

Dla wyższych stopni ciężko to wytłumaczyć bo też dzielimy jedną krawędź wstawiając na nią wierzchołek ale jak potem go połaczymy z dowolnym innym to powstaje cykl i trzeba ten cykl rozbić usuwając inną jego krawędź. Jednak wyszukiwanie cykli w drzewach to problem NP-trudny