Skip to interview prep
Apexed

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³).

How many spanning trees does the complete graph K_n have — Data structures & algorithms interview question — Apexed