TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 12

12) K_n denotes the complete graph with n vertices. Show that the number of spanning trees of K_n is nⁿ⁻²!

Hint: Use the matrix tree theorem and delete the first column a nd the first row of D(K_n)−A(K_n). Then add all rows (except the first) to the first one and observe that all entries of the new first row are equal to 1. Use the new first row to transform the matrix in such a way that the submatrix built of the second to the last row and second to the last column is diagonal matrix.

Solution

after using the hint we get a matrix $(D-A)'={\begin{pmatrix}1&1&1&1&\ldots \\0&n&0&0&\ldots \\0&0&n&0&\ldots \\0&0&0&n&\ldots \\\vdots &\vdots &\vdots &\vdots &\ddots \\\end{pmatrix}}$

we can now use the minors to calculate the determinant of the matrix. which leads to

$+1*{\begin{vmatrix}n&0&0&\ldots \\0&n&0&\ldots \\0&0&n&\ldots \\\vdots &\vdots &\vdots &\ddots \\\end{vmatrix}}-1*{\begin{vmatrix}0&0&0&\ldots \\0&n&0&\ldots \\0&0&n&\ldots \\\vdots &\vdots &\vdots &\ddots \\\end{vmatrix}}+1*\ldots$

except the first element all minor determinants are 0. The first determinant is $n^{n-2}$

--NeroBurner (Diskussion) 11:09, 22. Okt. 2013 (CEST)