235. How many spanning trees does the complete graph K_n have?
MediumGraph algorithms
Technical
Show model answer
Cayley's formula says K_n has n^(n−2) labeled spanning trees: K_3 has 3 and K_4 has 16. A clean proof uses Prüfer sequences, which give a bijection between labeled trees on n vertices and sequences of length n − 2 over n labels.
For an arbitrary graph, Kirchhoff's matrix-tree theorem counts spanning trees as any cofactor of the Laplacian matrix (degree matrix minus adjacency), computed with a determinant in O(n³).