graph - 令 N_k 表示 K_n 的生成树的数量

Question

问题：令 N_k 表示 K_n 的生成树的数量，其中顶点 n 的度数为 k，k = 1,2, 。. . ,n − 1（回想一下，我们假设 V(K_n) = {1,2, . . . ,n}）。(1) 证明 (n − 1 − k)N_k= k(n − 1)N_(k+1)。(2)利用(1)，导出N_k=$\left(\begin{array}{l}n-2 \ k-1\end{array}\right)(n-1)^{n-1-k }$.（乳胶）。(3) 由(2) 证明凯莱公式。

标签： graph