Hi everyone,
A well-known formula says that the number of spanning trees of a complete graph on n vertices is n[sup:6s2z9khr]n-2[/sup:6s2z9khr]. It is also possible to count the number of spanning trees using the Laplacian matrix of the graph by counting the determinant of its (n-1) submatrix.
It boils down to counting the determinant at the end of the post, the rest is just what I tried.
From wikipedia:
And verifying that it actually is n[sup:6s2z9khr]n-2[/sup:6s2z9khr] is what i'm trying to do, but it certainly doesn't seem as "easy" as they say
I've come up with this crazy recursive formula for calculating this by expanding the minors, but it doesn't seem to get any simpler (matrix with vertical lines means the determinant):
\(\displaystyle D^n_1 = -1\)
\(\displaystyle D^n_m = \begin{vmatrix}-1 & -1 & \cdots & -1 \\-1 & n & \cdots & -1 \\ \vdots & \ddots & \vdots \\-1 & -1 & \cdots & n \\ \end{vmatrix} = -K^n_{m-1}+(m-1)\cdot D^n_{m-1}\)
(the matrix has m rows)
\(\displaystyle K^n_1 = n\)
\(\displaystyle K^n_m = \begin{vmatrix}n & -1 & \cdots & -1 \\-1 & n & \cdots & -1 \\ \vdots & \ddots & \vdots \\-1 & -1 & \cdots & n \\ \end{vmatrix}= n\cdot K^n_{m-1} + (m-1)\cdot D^n_{m-1}\)
(the matrix has m rows)
\(\displaystyle L_n =\) number of spanning trees for a complete graph on n vertices = \(\displaystyle K^{n-1}_{n-1}\) and I'm trying to show that it's also = \(\displaystyle n^{n-2}\)
By putting in some numbers, it actually seems that \(\displaystyle L_n = n^{n-2}\), so it's precisely what it should be, but I have no idea how to prove that the recursive formulas actually sum up like that. So could someone help me show that the following determinant equals what it says?:
\(\displaystyle K^{n}_{n} = \begin{vmatrix}n & -1 & \cdots & -1 \\-1 & n & \cdots & -1 \\ \vdots & \ddots & \vdots \\-1 & -1 & \cdots & n \\ \end{vmatrix} = (n+1)^{n-1}\)
(n rows)
If there's a simpler way to do it that the one I started with, I'll be grateful to see it too.
Now I'm going to bed so I might not respond soon, but thanks in advance for any hints
A well-known formula says that the number of spanning trees of a complete graph on n vertices is n[sup:6s2z9khr]n-2[/sup:6s2z9khr]. It is also possible to count the number of spanning trees using the Laplacian matrix of the graph by counting the determinant of its (n-1) submatrix.
It boils down to counting the determinant at the end of the post, the rest is just what I tried.
From wikipedia:
And verifying that it actually is n[sup:6s2z9khr]n-2[/sup:6s2z9khr] is what i'm trying to do, but it certainly doesn't seem as "easy" as they say
I've come up with this crazy recursive formula for calculating this by expanding the minors, but it doesn't seem to get any simpler (matrix with vertical lines means the determinant):
\(\displaystyle D^n_1 = -1\)
\(\displaystyle D^n_m = \begin{vmatrix}-1 & -1 & \cdots & -1 \\-1 & n & \cdots & -1 \\ \vdots & \ddots & \vdots \\-1 & -1 & \cdots & n \\ \end{vmatrix} = -K^n_{m-1}+(m-1)\cdot D^n_{m-1}\)
(the matrix has m rows)
\(\displaystyle K^n_1 = n\)
\(\displaystyle K^n_m = \begin{vmatrix}n & -1 & \cdots & -1 \\-1 & n & \cdots & -1 \\ \vdots & \ddots & \vdots \\-1 & -1 & \cdots & n \\ \end{vmatrix}= n\cdot K^n_{m-1} + (m-1)\cdot D^n_{m-1}\)
(the matrix has m rows)
\(\displaystyle L_n =\) number of spanning trees for a complete graph on n vertices = \(\displaystyle K^{n-1}_{n-1}\) and I'm trying to show that it's also = \(\displaystyle n^{n-2}\)
By putting in some numbers, it actually seems that \(\displaystyle L_n = n^{n-2}\), so it's precisely what it should be, but I have no idea how to prove that the recursive formulas actually sum up like that. So could someone help me show that the following determinant equals what it says?:
\(\displaystyle K^{n}_{n} = \begin{vmatrix}n & -1 & \cdots & -1 \\-1 & n & \cdots & -1 \\ \vdots & \ddots & \vdots \\-1 & -1 & \cdots & n \\ \end{vmatrix} = (n+1)^{n-1}\)
(n rows)
If there's a simpler way to do it that the one I started with, I'll be grateful to see it too.
Now I'm going to bed so I might not respond soon, but thanks in advance for any hints