Trees and Spanning Trees
NBN Co engineers design fibre rollouts for regional NSW towns by finding spanning trees — connecting all premises with the fewest possible cables to minimise cost. A tree is a connected graph with no cycles, and exactly n−1 edges. This elegant property makes trees the foundation of network optimisation.
Practise this lesson
Three printable worksheets that build from foundations to mastery — or build your own from any module’s questions.
A network connects 6 offices. What is the minimum number of connections (edges) needed so every office can communicate with every other office?
Before reading on — write your prediction.
A tree is a connected graph with no cycles. A tree with $n$ vertices has exactly $n-1$ edges. A spanning tree of a network is a tree that includes every vertex — it connects everything with no redundant edges.
Tree: connected graph with no cycles. $n$ vertices → exactly $n-1$ edges.
Spanning tree: a subgraph that is a tree AND includes all vertices of the original network.
Leaf vertex: a vertex with degree 1 in a tree — attached by only one edge.
Key insight: removing any edge from a tree disconnects it. Adding any edge creates a cycle.
Key facts
- Tree: connected, no cycles, n−1 edges
- Spanning tree includes all vertices
- Leaf vertex has degree 1
Concepts
- Why n−1 is the minimum
- Why spanning trees are not unique
- Why trees avoid redundancy
Skills
- Verify a subgraph is a tree
- Count edges in a tree from n
- Identify spanning trees of a network
A tree satisfies three equivalent conditions — any two imply the third:
- Connected + no cycles.
- Connected + exactly $n-1$ edges.
- No cycles + exactly $n-1$ edges.
A leaf vertex has degree 1. Every tree with at least 2 vertices has at least 2 leaves.
Example check: A graph with 5 vertices and edges A–B, B–C, C–D, D–E. Is it a tree? Connected: yes (all reachable from A). Cycles: none. Edges: 4 = 5−1 ✓. It is a tree.
What to write in your book
- Tree: connected + no cycles + n−1 edges.
- Leaf: degree 1. Every tree has at least 2 leaves.
- Check: correct number of vertices, n−1 edges, connected, no cycles.
A spanning tree of a network G is any tree that:
- Uses all vertices of G.
- Uses only edges from G.
- Is connected with no cycles.
A network can have many spanning trees. To find one: start with all vertices, then add edges one at a time from the network, skipping any edge that would create a cycle. Stop when you have n−1 edges.
Example: A 4-vertex square network (A–B–C–D–A plus diagonal A–C). Spanning trees include: {A–B, B–C, C–D}, {A–B, A–C, C–D}, {A–B, A–D, A–C}, etc. Each has 3 edges (4−1=3).
What to write in your book
- Spanning tree: uses all vertices, only edges from original network, connected, no cycles.
- To find one: add edges one at a time, skip any that create a cycle.
- Multiple spanning trees exist — find any one that satisfies the conditions.
Spanning trees are used whenever you need to connect all nodes with the fewest edges (or minimum total cost). Real-world applications:
- Telecommunications: connect all buildings with minimum cable.
- Electrical grids: connect all substations without redundant lines.
- Road design: connect all towns with minimum road length.
In Lesson 5, we extend this to weighted networks and find the minimum spanning tree (lowest total weight). The structure here is the foundation.
What to write in your book
- Spanning tree = minimum connections to link all vertices.
- No cycles = no redundant connections.
- Next step: add weights → minimum spanning tree (Lessons 5).
Worked examples · reveal each step
A subgraph has 8 vertices and edges A–B, B–C, C–D, D–E, E–F, F–G, G–H. Is it a tree?
A tree has 12 vertices. How many edges does it have? What is the degree sequence if it is a path (chain)?
Network: 4 vertices A, B, C, D with edges A–B, B–C, C–D, D–A, B–D (a 4-cycle plus diagonal). Find a spanning tree.
- A tree has 15 vertices. How many edges does it have?
- A subgraph has 6 vertices and 6 edges and is connected. Is it a tree? Why or why not?
- For the network A–B, A–C, B–C, B–D, C–D, D–E: find two different spanning trees.
- Explain why adding any edge to a spanning tree creates a cycle.
For 6 offices: minimum connections = $6 - 1 = 5$. A spanning tree gives exactly this minimum — connecting everything with no redundant links. Your initial guess of 5 was correct if you applied n−1 instinctively!
Q1. A tree with n vertices has:
Q2. A connected graph with 7 vertices and 7 edges:
Q3. A spanning tree of a network with 10 vertices has how many edges?
Q4. Which of the following is TRUE about spanning trees?
Q5. A leaf vertex in a tree has degree:
SA 1. A tree has 20 vertices. (a) How many edges? (b) What is the sum of all vertex degrees? (2 marks)
SA 2. A network has 5 vertices and edges A–B, A–C, B–C, B–D, C–D. Find a spanning tree and state the edges you selected. (2 marks)
SA 3. Explain why a connected graph with n vertices and exactly n−1 edges must be a tree. What happens if you remove one edge? (3 marks)
Answers (click to reveal)
MC 1 — C: n−1 edges.
MC 2 — B: 7 vertices needs 6 edges for a tree; 7 edges means one extra → one cycle.
MC 3 — D: 10−1 = 9.
MC 4 — A: Multiple spanning trees exist.
MC 5 — B: Leaf = degree 1.
SA 1: (a) 19 edges [1]. (b) Sum = 38 [1].
SA 2: Any connected 4-edge subgraph with no cycles scores full marks, e.g. {A–B, A–C, B–D, B–C} — wait: verify no cycle. A–B, A–C, B–D, C–D: path A–C–D–B–A? Only if A–B is included. Check carefully [2].
SA 3: No cycles (n−1 edges insufficient for cycle) [1]; connected [1]; removing one edge disconnects [1].
Timed questions on trees, spanning trees and the n−1 edges rule.
⚔ Enter the arenaMark lesson as complete
Tick when you've finished the practice and review.