Mathematics Standard • Year 11 • Networks • Lesson 4
Trees & Spanning Trees · Build
Recognise a tree as connected and acyclic, then select a spanning tree.
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 · Test for a tree. A graph has V={A,B,C,D}, E={AB,BC,CD}. Is it a tree? State both properties to check. 3 marks
Q2 · Add an edge. Add DA to the graph above. Is the result a tree? Name the cycle. 2 marks
Q3 · Select a spanning tree. A graph has vertices A–E and edges AB,BC,CD,DE,EA,AC. Give one spanning-tree edge set. 2 marks
Q1 · Test for a tree
Yes. It is connected and has no cycle, so it is a tree.
Q2 · Add an edge
No. The added edge creates A–B–C–D–A, so the graph is not acyclic.
Q3 · Select a spanning tree
{AB,BC,CD,DE} is a connected chain through all five vertices with no cycle.