Matematyka.pl

Mam problem z zadaniem,

Z grafu pełnego \(\displaystyle{ K_{12}}\) usuwamy jedną krawędź, dowolną. Ile graf ma drzew spinających?

Nawet nie wiem od której strony ugryźć :/

Drzew spinających w \(\displaystyle{ K_n}\) jest \(\displaystyle{ n^{n-2}}\). Wszystkich krawędzi jest \(\displaystyle{ {n \choose 2}=\frac{n(n-1}{2}}\), a każda należy do tej samej ilości drzew spinających. Skoro więc każde drzewo ma \(\displaystyle{ n-1}\) krawędzi, to łączna ilość krawędzi we wszystkich drzewach to \(\displaystyle{ (n-1)n^{n-2}}\). Tak więc każda krawędź należy do:
\(\displaystyle{ \frac{(n-1)n^{n-2}}{\frac{n(n-1)}{2}}=2n^{n-3}}\)
drzew.
Jeśli więc usuniemy z grafu pełnego jedną krawędź, to odpadają nam wszystkie drzewa, które ją zawierały, musimy więc ich ilość odjąć od liczby wszystkich drzew. Tak więc odpowiedź to:
\(\displaystyle{ n^{n-2}-2n^{n-3}=(n-2)n^{n-3}}\)

Q.