Mathematics Standard • Year 11 • Networks • Lesson 4
Trees & Spanning Trees · Master
Use connectivity and cycle checks to evaluate spanning-tree claims.
Practice
Unless a question says otherwise, treat each network as a simple undirected graph: edges are unordered vertex pairs, with no loops or duplicate edges. Show your reasoning in the answer space; an edge list is enough.
Q1 · Diagnose a claim. A student selects AB,BC,CD,DE,EA for vertices A–E and calls it a spanning tree. Is the claim correct? 3 marks
Q2 · Repair the selection. Remove one edge from the selection above to make a spanning tree. Describe the result. 2 marks
Q3 · Use the definition carefully. A connected subgraph includes all 7 vertices but contains a cycle. Can it be a tree? Which tree condition does it fail? 2 marks
Q1 · Diagnose a claim
No. Those edges form cycle A–B–C–D–E–A, so the subgraph is connected but not acyclic.
Q2 · Repair the selection
Removing EA leaves A–B–C–D–E, a connected chain with no cycle.
Q3 · Use the definition carefully
No. It is connected but not acyclic. A tree must be both connected and acyclic, so the cycle disqualifies it.