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 onwrite 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.
A tree is a connected graph with no cycles and exactly n−1 edges (for n vertices). These three properties are equivalent: any two imply the third. Trees have no redundant connections, removing any edge disconnects the tree.
Pause, copy the three tree properties: (1) connected; (2) no cycles; (3) exactly n − 1 edges, and the equivalence statement: any two of these properties imply the third into your book.
We just saw that a tree is connected, has no cycles, and has exactly n − 1 edges, and that any two of these three properties imply the third. That raises a question: a tree is an abstract structure, what is the practical version of a tree that keeps all vertices of a real network connected while using the minimum number of edges? This card answers it → a spanning tree of network G contains all vertices of G, uses only edges from G, is connected with no cycles, and has exactly n − 1 edges, multiple spanning trees usually exist.
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).
Spanning tree of network G: contains all vertices of G, uses only edges from G, is connected with no cycles, and has exactly n−1 edges. A network can have many different spanning trees, they are not unique. All spanning trees have the same number of edges.
Pause, copy the spanning tree definition: contains all n vertices, uses only edges from the original network, is connected, has no cycles, and has exactly n − 1 edges, and note that a network can have many different spanning trees into your book.
We just saw that a network can have many different spanning trees, all with n − 1 edges but different total weights. That raises a question: multiple spanning trees exist, which one minimises total edge weight, and why does that matter in real problems? This card answers it → a minimum spanning tree (MST) is the spanning tree with the smallest total weight, used to minimise infrastructure cost (cable, pipe, road) while keeping all nodes connected.
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.
Spanning trees minimise connections: a minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. Used to minimise infrastructure cost while keeping all nodes connected. n nodes require exactly n−1 edges.
Pause, copy the minimum spanning tree (MST) purpose (minimise total edge weight while keeping all vertices connected, used for cheapest cable/pipeline layouts) and the key requirement (n − 1 edges for n vertices) into your book.
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.