The spanning trees count calculator gives the number of spanning trees of a complete graph with Cayley’s formula, of a complete bipartite graph, of a wheel and of a cycle, with the length of the Prüfer code and the number of edges of a tree.
How the calculation works
- Enter the vertices of the complete graph.
- Enter the two part sizes of the bipartite graph and the spokes of the wheel.
- Read the number of spanning trees for each graph.
Example
The complete graph on 6 vertices has 1,296 spanning trees, each with 5 edges and a Prüfer code of length 4. The complete bipartite graph K(3, 4) has 432. A wheel with 6 spokes has 320, and its rim cycle has 6.
Why it matters
The calculator helps students of graph theory and discrete mathematics, network designers and puzzle fans who want to count the ways of connecting a set of nodes with the minimum number of links, check Cayley’s formula on small cases, or compare the richness of different network shapes.
Good to know
The counts are for labeled vertices, so two trees that differ only by naming the vertices are counted separately. The numbers grow fast with the number of vertices, so the calculator limits the sizes. Use Kirchhoff’s theorem for graphs that are not in these families. The wheel formula uses the Lucas number rounded from the golden ratio, which is exact for the sizes allowed. The share shown compares with all subsets of edges of the right size. For a quick check, a complete graph on 3 vertices has 3 spanning trees, and a path or a star on any number of vertices has exactly one.
Related tools
The Turán graph calculator treats extremal graphs, the combinations calculator counts subsets, the binomial calculator gives coefficients and the Fibonacci calculator links to the Lucas numbers.