Question 12
Which statement is correct?
Not quite. A loop is an edge that starts and finishes at the same vertex. It reaches nothing new, so a tree never contains one, let alone must. In 2021, 3.0% of Queensland students chose (A).
Not quite. A tree is connected and has no cycles. Any cycle would contain an edge you could remove and still reach every vertex, and removing it would make the total weight smaller. In 2021, 9.9% of Queensland students chose (B).
Not quite. When some edges have equal weights, a network can have more than one minimum spanning tree. The minimum total weight is always the same, yet different sets of edges can reach it. One way to get this is to treat “the minimum weight is unique” as if it meant “the tree is unique”. In 2021, 28.9% of Queensland students chose (C).
That’s it. Step through the hints below to see why. In 2021, 57.2% of Queensland students chose (D).
Build a spanning tree for this network. Switch edges on and off and watch the counts.
Know the words. A loop is an edge from a vertex back to itself. A cycle is a path that returns to its starting vertex without reusing an edge.
A tree is a connected graph with no cycles, and so no loops either. A minimum spanning tree is a tree that reaches every vertex with the smallest total weight. (A) and (B) say “must contain”, which is the opposite of what makes it a tree.
Count as you build. Start with one vertex. Every edge you add without making a cycle brings in exactly one new vertex.
$$\text{vertices}=\text{edges}+1\qquad\text{so}\qquad\text{edges}=v-1$$
That is statement (D) in different words. The network on the left has 5 vertices, so every spanning tree you build has 4 edges.
Now test (C). Press the orange button on the left twice. The edges QR and QT both weigh 5, and either one finishes the tree.
Two different trees, the same minimum total weight. One network with two minimum spanning trees is enough to make “every network has only one” false.
- (A) False. A tree has no loops.
- (B) False. A tree has no cycles.
- (C) False. Equal weights can give more than one minimum spanning tree, all with the same total weight.
- (D) True. A tree with $v$ vertices has $v-1$ edges, so it has one more vertex than edges.
Only mark this done when you could do it without help. Reading the solution does not count.
Question wording is from the 2021 QCAA General Mathematics external assessment, © State of Queensland (QCAA) 2021, licensed under CC BY 4.0, and has been adapted. Tangent Tuition is not affiliated with the QCAA.
Spot a mistake on this page? Report it