Calculating number of spanning trees of complete graph with each edge divided

49 Views Asked by At

When calculating the number of spanning trees of complete graph $K_n$ with adding an extra vertex to every edge, I've noticed that the number of spanning trees is always equal to:

$$n^{n - 2}*2^{n - 1\choose 2}$$

I understand that $n^{n - 2}$ comes from Cayley's formula, but why $2^{n - 1\choose 2}$?

Thanks.