A tree is the leanest possible way to keep a set of vertices connected -- remove any edge and it falls apart, add any edge and a cycle appears. Applying that same idea to a bigger, already-connected graph gives a spanning tree: the fewest edges that still reach every vertex. Both the shape of a single tree and the count of how many different trees exist come back constantly later in this course, from minimum spanning tree algorithms to network design.
A tree is the minimal skeleton that still holds a structure together: cut any one connection and it splits into two pieces; add any one extra connection and a loop appears where none existed before. A spanning tree takes a bigger, already-connected network and strips it down to that same minimal skeleton -- keep only the edges needed to still reach everyone, throw away every edge whose removal wouldn't disconnect anything. Cayley's formula answers a totally different question: forget any particular network, and just ask how many different tree shapes could possibly be built on a fixed set of labeled dots. That number turns out to have a remarkably clean formula for how fast it grows.
A tree is a connected graph with no cycles. A spanning tree is a subgraph of a connected graph G that applies that same idea on top of an existing graph: it includes every vertex of G, uses only edges already present in G, and is itself a tree. Because it's a tree, the edge-count theorem applies to it directly -- a spanning tree of an n-vertex graph always has exactly n-1 edges, regardless of how many extra edges G itself has lying around unused.
A connected graph typically has more than one valid spanning tree (different choices of which edges to keep), and counting exactly how many labeled trees exist in the first place -- with no underlying graph constraining the choice at all, just n labeled vertices and every possible tree shape on them -- is itself a clean counting question. Cayley's formula is that closed-form answer: the number of distinct labeled trees on n vertices, and it grows strikingly fast even for small n.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics II — Combinatorics
A spanning tree of a graph G must:
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A spanning tree reaches every vertex with the fewest possible edges -- exactly n-1, never every edge of G.
From Discrete Mathematics I — Logic, Proof, and Structure
A graph with vertices A, B, C has edges AB, BC, and AC (a triangle). Which edge subset is a valid spanning tree?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
All three edges together form the cycle itself -- not acyclic, so not a tree.
One edge alone leaves C unreached -- not every vertex is included.
A triangle is connected, so it does have spanning trees -- just not using all three edges at once.
Why
{AB, BC} includes all three vertices, uses only edges already in the graph, and is acyclic -- a valid spanning tree with 3 - 1 = 2 edges.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics II — Combinatorics
How many spanning trees does the complete graph K5 have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Spanning trees of K5 are exactly the labeled trees on 5 vertices: 5^3 = 125.
Correct answer
Also accepted:
Why
Recognize that the spanning trees of K5 are exactly the labeled trees on those same 5 vertices.
From Discrete Mathematics II — Combinatorics
A lab needs one test case per labeled tree on 7 vertices. How many test cases is that?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
7^(7-2) = 7^5 = 16807.
Correct answer
Also accepted:
Why
Translate 'one test case per labeled tree' into a request for Cayley's count with n=7.
Theorem
The Tree Edge-Count Theorem
also known as: n vertices, n-1 edges
Recalled from Discrete Mathematics I — Logic, Proof, and Structure · Properties of trees — first taught there.
Every tree on n \geq 1 vertices has exactly n - 1 edges.
Induct on n. A tree with n = 1 vertex has no edges at all, and n - 1 = 0, so the base case holds.
Assume every tree on k vertices has exactly k - 1 edges, for some k \geq 1. Let T be a tree on k + 1 vertices. Every tree with more than one vertex has at least one leaf (a vertex of degree 1) — following any path outward without repeating a vertex must eventually stop somewhere, since T is finite and acyclic, and it can only stop at a vertex with no unused edge left, degree 1. Remove that leaf v and its single incident edge. What remains is still connected (no other vertex's connections ran through v, since v had only one edge) and still acyclic (deleting a vertex can't create a cycle), so it is a tree on k vertices. By the inductive hypothesis it has k - 1 edges. Adding v's one edge back gives T exactly (k - 1) + 1 = k edges, which is (k+1) - 1, as required.
By induction, every tree on n vertices has n - 1 edges for all n \geq 1.
Theorem
Cayley's Formula
also known as: the labeled tree count
Recalled from Discrete Mathematics II — Combinatorics · Cayley's formula, stated — first taught there.
The number of labeled trees on n \geq 2 vertices is n^{n-2}.
We sketch the Prüfer correspondence, a bijection between labeled trees on the vertex set \{1, \ldots, n\} and sequences of length n-2 whose entries come from \{1, \ldots, n\}. Since there are n^{n-2} such sequences, the bijection proves the count.
Tree to sequence. Given a tree T on \{1, \ldots, n\}, repeat the following step n-2 times: find the leaf with the smallest label, write down the label of its unique neighbor, and delete the leaf. The n-2 recorded neighbor labels, in order, form the Prüfer sequence of T. The process is deterministic, so each tree yields exactly one sequence.
Sequence to tree. Given a sequence (a_1, \ldots, a_{n-2}), the degree of each vertex v in the corresponding tree must be one plus the number of times v appears in the sequence: every non-leaf vertex is recorded once for each of its leaf-neighbors deleted while it remains, and once more when it is itself deleted or survives at the end. Rebuild the tree by reversing the deletions: at step i, join a_i to the smallest-labeled vertex that is not among a_i, a_{i+1}, \ldots, a_{n-2} and has not yet been used, then mark that vertex used. After n-2 joins, exactly two vertices remain unused; join them to each other. Each step is forced, so each sequence yields exactly one tree, and rebuilding the sequence's tree recovers the original sequence.
The two maps are mutually inverse, giving a bijection. Hence the number of labeled trees on n vertices equals the number of sequences of length n-2 over an alphabet of size n, which is n^{n-2}. Small cases confirm it: n = 3 gives 3^1 = 3 trees (the three paths on three labeled vertices), and n = 4 gives 4^2 = 16.
Confirm n vertices means n-1 edges
Count the nodes in this tree, then count its edges, and confirm the edge count is exactly one less.
Loading interactive…
Worked example
Counting a spanning tree's edges without drawing it
-
1
A connected graph has 18 vertices. Without seeing any spanning tree of it drawn out, how many edges does every one of its spanning trees have?
-
2
The tree edge-count theorem depends only on the vertex count, never on which particular edges got chosen or how many extra edges the original graph had.
-
3
Apply |E| = n - 1 with n = 18.
-
4\boxed{17 \text{ edges, in every spanning tree of this graph}}
Loading interactive…
Worked example
Rejecting a subgraph that can't be a spanning tree
-
1
A connected graph has 7 vertices. A proposed spanning tree for it is listed with 5 edges. Is that possible?
-
2
Every spanning tree on 7 vertices needs exactly 7-1=6 edges, by the tree edge-count theorem -- no exceptions for which 6 edges get picked.
-
3
Compare the claimed count to the required count directly.
-
4\boxed{\text{No} - \text{it needs 6 edges, not 5}}
A 5-edge subgraph on 7 vertices can't even be connected, which already rules it out as a spanning tree before checking whether it has a cycle.
Loading interactive…
Worked example
Applying Cayley's formula to a specific vertex count
-
1
How many different labeled trees exist on 5 vertices?
-
2
Cayley's formula counts every possible tree shape on n labeled vertices, with no other graph constraining which edges are allowed -- apply it directly with n=5.
-
3n^{n-2} = 5^{5-2} = 5^3
-
4\boxed{125 \text{ labeled trees}}
Compare this to the tree edge-count theorem: every single one of these 125 trees still has exactly 5-1=4 edges -- Cayley's formula counts how many trees exist, the edge-count theorem fixes a fact true of every one of them.
Where this goes next
Network reliability and design
A telecom company's minimum-cost backbone connecting n sites is a spanning tree of the full graph of candidate links -- using exactly n-1 links is the theoretical floor for staying connected with zero redundancy, and every additional link beyond that buys fault tolerance at a real, countable cost. Cayley's formula is what tells a network designer, before comparing costs at all, just how enormous the space of possible tree layouts actually is: even a modest 10-site network already has 10^{8} = 100{,}000{,}000 possible spanning-tree shapes to choose among, which is exactly why Chapter 10's algorithms (Kruskal's, Prim's) exist -- searching that space by hand is not an option.
Check your understanding (counts toward your progress)
A connected graph has 12 vertices. How many edges does any one of its spanning trees have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The tree edge-count theorem applies to any spanning tree directly: n - 1 = 12 - 1 = 11.
Correct answer
Also accepted:
Why
A connected graph has 15 vertices and 19 edges. How many edges must be removed (without disconnecting the graph) to reach a spanning tree?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A spanning tree needs 15-1=14 edges. Removing 19-14=5 carefully-chosen edges (each one whose removal doesn't disconnect the graph) reaches that target.
Correct answer
Also accepted:
Why
Compute the spanning tree's target edge count from the vertex count alone, before subtracting from the 19 edges given.
A proposed spanning tree of a 6-vertex graph is listed with edges forming a cycle. What went wrong?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A tree is defined as connected AND acyclic -- a cycle disqualifies it immediately, regardless of anything else.
Vertex count isn't the issue described.
A cycle actually means there's likely one edge too many for a tree on this many vertices, not too few.
Why
A tree cannot contain a cycle by definition -- any subgraph with a cycle fails to be a tree at all, let alone a spanning tree, no matter how many vertices it reaches.
Recall the two properties a tree must have, together.
Check the proposed subgraph against whichever of those two properties a cycle would violate.
A connected graph's spanning tree loses one of its own edges (imagine it fails or is cut). What happens to the graph restricted to just that spanning tree's edges?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A tree has no redundant edges at all -- there's no backup path to fall back on.
Removing an edge can never create a cycle -- only adding one can.
Every edge in a tree is load-bearing -- removing any one of them changes the structure.
Why
Every edge of a tree is a bridge -- since there's exactly one path between any two vertices, removing any single edge severs that one path and splits the tree into exactly two pieces.
Recall how many paths exist between any two vertices in a tree to begin with.
Ask what removing the one and only path between some pair of vertices does to their ability to reach each other.
Practice: Spanning trees and the edge-count theorem (4 problems · doesn’t affect your progress)
A connected graph has 9 vertices. How many edges does any spanning tree of it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The tree edge-count theorem: 9-1=8.
Correct answer
Also accepted:
Why
Does a spanning tree ever use an edge that isn't part of the original graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A spanning tree is a subgraph of the original graph -- it can only use edges that were already there.
No -- a spanning tree only ever uses edges the original graph already has
A connected graph has 7 vertices and 9 edges. How many edges must be removed to leave a spanning tree?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A spanning tree needs 7-1=6 edges; removing 9-6=3 reaches that count.
Correct answer
Also accepted:
Why
Figure out how many edges a spanning tree of 7 vertices must have before subtracting from the graph's actual 9.
A connected graph already has exactly n-1 edges. How many distinct spanning trees does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A connected graph with exactly n-1 edges is already a tree, and a tree's only spanning tree is itself -- there's no extra edge to leave out in a different way.
Recall what having exactly n-1 edges and being connected already makes a graph.
Ask how many spanning trees a graph that is already a tree could possibly have besides itself.
Exactly one -- itself
Check your understanding (counts toward your progress)
What does Cayley's formula count exactly?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That's a different (and generally harder) question, since it depends on which specific graph's edges are available to choose from.
Edge count is fixed by the tree edge-count theorem (n-1), a completely different fact from Cayley's formula.
Leaf count varies tree to tree and isn't what this formula measures.
Why
Cayley's formula counts every possible tree shape on n labeled vertices with no underlying graph restricting which edges are allowed -- a pure counting question about trees in the abstract.
Ask whether the formula assumes one specific graph's own edges, or every possible edge between the labeled vertices.
Six labeled vertices, no constraints at all on which pairs may be joined -- how many different tree shapes could be built on them?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
With n=6, the formula gives 6^{6-2}=6^4=1296 -- a jump from the 125 trees on 5 vertices, showing how fast this count accelerates.
Correct answer
Also accepted:
Why
Plug n=6 into Cayley's formula's exponent pattern -- n^{n-2} -- before doing the arithmetic.
How many distinct labeled trees exist on 3 vertices?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Plug n=3 into Cayley's formula: 3^{3-2}=3^1=3 -- and indeed, the three paths through three labeled vertices are the only tree shapes possible.
Correct answer
Also accepted:
Why
Two different network designers each independently propose a spanning tree for the same 10-site graph. Does Cayley's formula tell you how many of the 10^{8} abstract tree shapes are actually valid spanning trees of their specific graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Cayley's formula assumes every possible edge is available; a real graph usually has far fewer edges than that, so only some of the 10^8 abstract tree shapes will actually be buildable from its specific edge set.
Ask whether Cayley's formula's count assumes every possible edge is available, or only the edges one particular graph happens to have.
Practice: Counting labeled trees (4 problems · doesn’t affect your progress)
How many labeled trees exist on 2 vertices?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n^{n-2}=2^{0}=1 -- the single edge joining the two vertices is the only possible tree.
Correct answer
Also accepted:
Why
On 5 vertices, how many distinct labeled trees can you form?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n^{n-2}=5^{3}=125.
Correct answer
Also accepted:
Why
Set up Cayley's formula with n=5 first, then work out the exponent before multiplying anything out.
Cayley's formula assumes what about which edges are available to build a tree from?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The formula counts every tree shape achievable with no restriction at all on which pairs may be joined -- the abstract count, not one graph's spanning-tree count.
Ask whether the formula restricts itself to one graph's actual edges, or allows every possible pairing between the labeled vertices.
Every possible edge between any pair of the n labeled vertices
Count the labeled trees possible on 7 vertices.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n^{n-2}=7^{5}=16{,}807.
Correct answer
Also accepted:
Why
Identify n in this problem, and set up the exponent Cayley's formula uses, n-2.
Compute 7 raised to that exponent.