Trees, minimum spanning trees and Prim's algorithm: VCE General Mathematics Unit 4 Networks and decision mathematics

What this dot point is asking

The Study Design's "Trees and minimum connector problems" topic has three parts: "trees and spanning trees", "minimum spanning trees in a weighted connected graph and their determination by inspection or by Prim's algorithm", and "use of minimal spanning trees to solve minimal connector problems". A minimal connector problem asks for the cheapest (or shortest) set of links that joins every location: cabling buildings, piping houses, sealing roads between towns.

You need to:

1. recognise a tree and know its properties;
2. find a spanning tree of a graph;
3. find a minimum spanning tree by inspection or by Prim's algorithm, from a network diagram or a table, and give its weight;
4. handle variations: an edge that must be included, an unknown weight, a new edge.

These are usually one-mark multiple-choice questions (2023 Examination 1 Question 35, $74\%$; 2025 Examination 1 Question 35, $65\%$) or a short part of an Examination 2 networks question.

The answer

Trees

A tree is a connected graph with no cycles. Every tree with $n$ vertices has:

• exactly $n - 1$ edges;
• exactly one path between any two vertices;
• a sum of degrees of $2(n - 1)$, because every edge adds 2 to the degree sum;
• at least two vertices of degree 1 (if $n \ge 2$).

Removing any edge from a tree disconnects it (every edge is a bridge), and adding any edge between two of its vertices creates exactly one cycle. For planar graphs, a tree has one face, so Euler's formula $v + f = e + 2$ becomes $n + 1 = (n - 1) + 2$, which checks out.

Spanning trees

A spanning tree of a connected graph is a subgraph that includes every vertex and is a tree. A graph usually has many spanning trees. If the graph has $n$ vertices and $e$ edges, a spanning tree keeps $n - 1$ of them, so $e - (n - 1)$ edges are removed, each one breaking a cycle without disconnecting anything. When you draw one, use only edges from the original graph (in 2025 Examination 2 Question 15d, $81\%$ succeeded; some lost the mark by adding an edge that was not in the graph).

Minimum spanning trees

In a weighted graph, a minimum spanning tree is a spanning tree with the smallest total weight. It is the answer to every minimal connector problem. There may be more than one minimum spanning tree when some weights are equal, but they all have the same total.

Prim's algorithm

1. Start at any vertex. It is the tree so far.
2. Look at every edge that joins a vertex in the tree to a vertex not yet in the tree. Add the one with the smallest weight (if there is a tie, either will do).
3. Repeat step 2 until all $n$ vertices are in, which takes $n - 1$ edges.

Because each new edge always goes to a new vertex, Prim's algorithm can never create a cycle. The starting vertex can change the order in which edges are added, but not the total.

In the figure, starting at $A$: $AC = 5$; then from $\{A, C\}$ the cheapest is $CD = 6$; then $DE = 5$; then $EG = 6$; then $AB = 7$ and $DF = 7$ (tied, either first). Total $5 + 6 + 5 + 6 + 7 + 7 = 36$.

Finding it by inspection

For small networks (and most multiple-choice questions), list the edges from smallest to largest and add them one at a time, skipping any edge that would complete a cycle, until you have $n - 1$ edges. This greedy method always gives a minimum spanning tree. It adds edges in a different order from Prim's, so use Prim's whenever a question asks for "the order in which Prim's algorithm adds the edges".

Prim's algorithm from a table

Networks are often given as a table of weights, with a dash for "no direct link". The method is unchanged:

1. Circle the starting vertex. Its row lists the edges from it.
2. Among the rows of all vertices already chosen, pick the smallest weight leading to a vertex not yet chosen.
3. Add that vertex and repeat, ignoring entries between two chosen vertices.

Record each edge as you add it; the list is both your working and the answer.

Forced edges, unknown weights and new edges

• An edge must be included (an existing road, a fixed link): put it in first, then carry on choosing the cheapest edges that avoid cycles. The total can only stay the same or rise.
• An unknown weight $w$ is in the tree (2025 Examination 1 Question 35): include $w$ first, find the other $n - 2$ edges, and write the length as a number plus $w$.
• A new edge is proposed: it enters the tree only if it is lighter than the heaviest edge on the cycle it would create with the tree.

Minimum spanning tree or shortest path?

A minimum spanning tree connects all vertices at least total cost. The route it gives between two particular vertices is often not the shortest route between them. In the figure, the tree route from $B$ to $G$ is $7 + 5 + 6 + 5 + 6 = 29$, but the direct path $B$-$E$-$G$ is only $12 + 6 = 18$. "Connect everything" means minimum spanning tree; "quickest way from here to there" means shortest path (Dijkstra's algorithm).