Trees reappear in this course's closing chapters as objects to count — how many spanning trees a graph has, Cayley's formula for how many labeled trees exist on n vertices — so the edge-count fact underneath every one of those results is worth having cold before it's leaned on.
A tree is the minimal skeleton that still holds everything together. Remove any single edge and it falls into two pieces. Add any single edge and a cycle appears. A spanning tree applies that same idea to a bigger graph. Strip away every extra edge, the ones creating cycles. What's left is the fewest edges that still reach every vertex. A well-connected graph usually has more than one valid way to strip it down this way. Different choices of which edges to keep can all count as equally good spanning trees. Asking how many different ways there are is a genuine counting question of its own.
A tree is a connected graph with no cycles; a spanning tree of a connected graph G is a subgraph that includes every vertex of G, uses only edges from G, and is itself a tree. The edge-count theorem — every tree on n vertices has exactly n-1 edges — is the single fact Chapter 11 builds a whole enumeration program on: it's the reason a spanning tree is "just enough" edges to stay connected, one fewer edge than that and the graph disconnects, one more and a cycle appears. A connected graph can have many different spanning trees at once — any n-1 edges that keep every vertex reachable and introduce no cycle qualify — and counting exactly how many a given graph has is precisely the enumeration problem Chapter 11 solves in general.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Which statement about trees is true?
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.
Two distinct paths between the same pair of vertices would trace out a cycle, which a tree cannot contain.
A tree has no cycles at all, by definition.
A single vertex with no edges is trivially connected and acyclic -- it is a tree with n = 1.
Why
Connectedness guarantees at least one path between any two vertices, and acyclicity rules out a second one -- so the path is always unique.
From Discrete Mathematics I — Logic, Proof, and Structure
A tree T has an edge e between vertices u and v. Removing e from T produces what?
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.
Removing any edge from a tree always disconnects it -- that edge was the only path between the vertices on either side.
Removing an edge can never create a cycle -- fewer edges can only break connections, not add loops.
Both resulting pieces can have more than one vertex -- the split depends on where e sits in the tree, not always at a leaf.
Why
Every edge of a tree is the unique connection between the vertices on its two sides, so deleting it always splits the tree into exactly two connected pieces, each acyclic and therefore itself a tree.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
A weighted connected graph has more than one minimum spanning tree. What must be true?
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.
Negative weights are not required for multiple minimum spanning trees to exist.
A minimum spanning tree can only exist if the graph is connected in the first place.
If every spanning tree had equal weight, there would be no notion of 'minimum' setting some apart -- multiple ties at the smallest weight is the actual requirement.
Why
Multiple minimum spanning trees exist exactly when at least two distinct spanning trees achieve the same smallest possible total weight, often caused by ties among edge weights during selection.
From Discrete Mathematics I — Logic, Proof, and Structure
A network has vertices A, B, C, D, E and edges AB=4, AC=2, BC=1, BD=5, CD=3, DE=6. What is the minimum spanning tree total weight?
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.
Close, but recheck which edges the greedy selection actually keeps among A, B, C.
That total double-counts or includes an edge the minimum selection actually skips.
That is the sum of every edge in the graph, not the minimum spanning tree.
Why
Keep the two cheapest edges among the A-B-C cycle (BC=1, AC=2, dropping AB=4), then CD=3 to reach D, then the only edge to E, DE=6: total 1+2+3+6 = 12.
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.
Confirm n vertices means n-1 edges
Read off the number of nodes in this tree, then count its edges and confirm the count is one less.
Loading interactive…
Worked example
Counting edges without drawing them all
-
1
A network diagram is known to be a tree with 41 nodes. Without seeing the diagram, how many connections (edges) does it have?
-
2
The tree edge-count theorem needs only the vertex count, never the tree's actual shape.
-
3
Apply |E| = n - 1 with n = 41.
-
4\boxed{40 \text{ edges}}
Loading interactive…
Worked example
Spotting a non-spanning subgraph
-
1
A connected graph has 5 vertices. A proposed spanning tree for it is listed with only 3 edges. Is that possible?
-
2
Every spanning tree on 5 vertices needs exactly 5-1=4 edges, by the tree edge-count theorem — no exceptions for which 4 edges are chosen.
-
3
Compare the claimed edge count to the required count.
-
4\boxed{\text{No} - \text{it needs 4 edges, not 3}}
A 3-edge subgraph on 5 vertices cannot even be connected, let alone a spanning tree.
Loading interactive…
Where this goes next
Network reliability
A telecom network's minimum-cost backbone is a spanning tree of the full candidate-link graph — using exactly n-1 links to reach n sites is the theoretical floor for staying connected with no redundancy at all. Every additional link beyond that n-1 buys fault tolerance (a backup path if one link fails) at a real, countable cost, which is exactly the trade-off spanning-tree algorithms like Kruskal's and Prim's (Chapter 11, later in this course's backlog) are built to optimize.
Check your understanding (counts toward your progress)
What happens if a single new edge is added between two existing vertices of a 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
The tree already has a unique path between any two vertices; adding a direct edge between them closes that path into a cycle.
A tree already has exactly one path between any two vertices -- think about what a second, direct connection between those same two vertices creates alongside that existing path.
What happens if a single edge is removed from a 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
Every edge in a tree is a bridge -- removing any one disconnects the tree into exactly two pieces, since there's no alternate path around it.
Recall that a tree has exactly one path between any two vertices, with no alternate route -- think about what removing that single path's edge does to reachability.
A connected graph has 12 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
A spanning tree on 12 vertices has 12-1=11 edges, regardless of how many edges the original graph had.
Correct answer
Also accepted:
Why
Apply the tree edge-count theorem directly to the number of vertices -- the original graph's own edge count is irrelevant.
A tree has 27 vertices. How many edges 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
Every tree on n vertices has exactly n-1 edges: 27-1=26.
Correct answer
Also accepted:
Why
Practice: Trees, spanning trees, and their edge count (5 problems · doesn’t affect your progress)
Which property distinguishes a tree from a general connected 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.
Trees have exactly n-1 edges -- fewer than vertices, not more.
Nothing about tree size caps at 10 -- trees exist at any size.
Whether edges cross in a drawing is a layout choice, not a defining property of the underlying graph.
Why
A tree is specifically a connected graph with no cycles -- that acyclic property is exactly what separates it from other connected graphs.
A tree has no cycles
A tree has 27 vertices. How many edges 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
Every tree on n vertices has exactly n-1 edges: 27-1=26.
Correct answer
Also accepted:
Why
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.
Include every vertex of G, using only edges from G, forming a tree
A connected graph has 9 vertices and 14 edges. How many edges must be removed to turn it into 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 on 9 vertices needs 9-1=8 edges. Removing 14-8=6 edges (the ones creating cycles) leaves a spanning tree.
Correct answer
Also accepted:
Why
First find how many edges a spanning tree on 9 vertices needs, then subtract that from the 14 edges already there.
A graph has 6 vertices and 6 edges, and someone calls it a tree. What's the fastest way to know this is wrong, without drawing it?
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 edge-count theorem fixes a tree's edge count at exactly n-1 -- here, 5. Six edges among six vertices is one too many, and that extra edge always closes a cycle somewhere, disqualifying it as a tree.
Apply the edge-count theorem to find exactly how many edges a 6-vertex tree is allowed to have.
Compare that number to the 6 edges actually given, and think about what one edge beyond that count always creates.
A tree on 6 vertices must have exactly 5 edges -- 6 edges is one too many, which forces a cycle