Skip to content
Omnikalc

Spanning trees count calculator

Enter the number of vertices of a complete graph, the sizes of the two parts of a complete bipartite graph and the number of spokes of a wheel to get the number of spanning trees of each.

Updated on
Your inputs

Value out of range

Value out of range

Value out of range

Value out of range

Results

Spanning trees of the complete graph

1,296

Spanning trees of the complete bipartite graph

432

Spanning trees of the wheel

320

Spanning trees of the cycle on the same rim
6
Length of the Prüfer code of the complete graph
4
Edges of each spanning tree of the complete graph
5
Spanning trees as a share of all edge subsets of the same size
43.1568 %

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.

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.

Frequently asked questions

What is Cayley’s formula?

Cayley’s formula says that the complete graph on n labeled vertices has exactly n^(n−2) spanning trees. For n = 4 there are 16 labeled trees, for n = 5 there are 125 and for n = 6 there are 1,296. It was stated by Cayley in 1889, and Prüfer gave a proof with a bijection between trees and sequences of length n − 2.

How are the spanning trees of a bipartite graph counted?

For the complete bipartite graph K(m, n), the number of spanning trees is m^(n−1) × n^(m−1). For K(3, 4) it is 3³ × 4² = 432. For m = 1 it is a star with only one spanning tree, which is the graph itself.

What about the wheel?

A wheel with w spokes has w + 1 vertices: a hub joined to all the vertices of a cycle of w vertices. Its number of spanning trees is L(2w) − 2, where L is the Lucas number. For w = 6 it is L(12) − 2 = 322 − 2 = 320. The sequence 3, 4... for w ≥ 3 begins 16, 45, 121, 320.

Why are spanning trees counted?

Spanning trees describe the ways to connect all the nodes of a network with the fewest links. The number measures the robustness of a network design, it enters reliability calculations and electrical network analysis, and Kirchhoff’s matrix tree theorem counts them for any graph from the determinant of the Laplacian.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.