Spanning Tree Count Calculator
For the complete graph K_n, where every one of n labeled vertices connects directly to every other, Cayley's formula gives the exact number of distinct spanning trees: n^(n-2). Enter n below for the exact count and the formula used to get it.
Cayley's Formula: Why n^(n-2)
The complete graph K_n has an edge between every pair of its n vertices. A spanning tree picks exactly n−1 of those edges so every vertex stays connected with no cycles. Arthur Cayley proved in 1889 that K_n has exactly n^(n−2) distinct labeled spanning trees — a closed-form shortcut to what would otherwise be a hard edge-by-edge count.
By convention n=1 gives 1 trivial tree and K_2 (n=2) gives 1 (its only edge); from there the formula takes over: n=3 gives 3, n=4 gives 16, n=5 gives 125.
Worked Example: K_4 Has Exactly 16 Spanning Trees
Label four vertices 1, 2, 3, 4. Cayley's formula gives 4^(4−2) = 4^2 = 16. You can verify this by listing the shapes directly: a labeled tree on 4 vertices is either a path (a chain through all four) or a star (one center connected to the other three).
There are 4!/2 = 12 distinct labeled paths and 4 distinct labeled stars (one for each possible center) — 12 + 4 = 16, matching the formula exactly.
This Counts Trees, It Doesn't Find the Lightest One
A common mix-up: "spanning tree" calculators are often expected to solve the weighted minimum spanning tree problem — the lowest-cost edge set connecting a specific weighted graph, the job of Prim's or Kruskal's algorithm, which needs concrete edges and weights as input.
This calculator answers a different, purely combinatorial question: given only the vertex count n of a complete graph, how many distinct spanning trees exist in total? Same name, different method.
Frequently Asked Questions
What does this calculator count?
The number of distinct labeled spanning trees of the complete graph K_n, where all n vertices are already connected to each other. It's a pure combinatorial count, not a weighted minimum spanning tree search.
What is Cayley's formula?
Cayley's formula states that a complete graph on n labeled vertices has exactly n^(n-2) distinct spanning trees. For n=4 that's 4^2=16; for n=5 it's 5^3=125.
Does this tool find the minimum spanning tree of my own weighted graph?
No. Finding a minimum-weight spanning tree in a graph with edge weights needs an algorithm like Prim's or Kruskal's, which requires the actual edges and weights as input. This calculator only counts how many spanning trees a complete graph of a given size has.
How many spanning trees does a cycle have?
A cycle graph C_n (n vertices in a ring) has exactly n spanning trees - one for each edge you could remove to break the single loop into a tree.
Why does the count grow so fast with n?
Because n^(n-2) is exponential: K_5 has 125 spanning trees, and K_10 has 10^8 = 100,000,000. Each added vertex multiplies the possibilities.