Number of undirected trees with $k$ vertices

116 Views Asked by At

If the number of undirected trees with $k$ vertices on a vertex set $V=\{1,\dots,k\}$ is $f(k) = k^{k-2}$ and the number of those who don't contain the edge $1-2$ is $(k-2)^{k-3}$, then why is the number of undirected trees with $n$ vertices containing the edge $1-2$: $g(k) = 2k^{k-3}$ ?

1

There are 1 best solutions below

7
On

By symmetry, every possible edge is in the same number of spanning trees, and each spanning tree contains exactly $k-1$ edges. Use this and the fact you cited to conclude.