Any connected network can have edges removed, taking care not to disconnect the network, until the result is a subnetwork that is a tree - this is then called a spanning tree. Here’s an example:

The network in the centre has its eight different spanning trees arranged around it. You can still get from one vertex to any other, but you can’t get back without repeating an edge.

A connected network that isn’t already a tree always has multiple spanning trees. This network:

This network has weight $4+6+5+2+3+10=30$4+6+5+2+3+10=30

… has $11$11 spanning trees. Here they all are, with their weights:

Weight $24$24	Weight $18$18	Weight $25$25
Weight $22$22	Weight $23$23	Weight $15$15
Weight $21$21	Weight $22$22	Weight $21$21
Weight $20$20	Weight $14$14

The last spanning tree is special, since it has the lowest weight out of all of them. This is called the minimal spanning tree. Sometimes there can be two or more spanning trees with equal lowest weight, in which case they are all minimal spanning trees.

Here’s a network with two minimal spanning trees:

Can you find both of them? It can be quite hard, and take a long time.

Practice question

Question 1

Consider the following graphs.

Which of these graphs is a tree?
A
B
C
Why is the following graph not a tree?

It is disconnected.
A
It has a loop.
B
It has multiple edges connecting the same vertices.
C
it has a cycle.
D
Why is the following graph not a tree?

It has a loop.
A
It is disconnected.
B
It has a cycle.
C
It has multiple edges connecting the same vertices.
D

Prim’s algorithm

Sometimes it is very impractical to find a minimal spanning tree by eye. Consider the following network which represents a mycorrhizal nutrient transfer system:

These underground connections are created and maintained by fungus to connect and nurture the roots of plants (represented here by the vertices) under the ground. The weights represent distance in metres.

A severe drought is affecting the area, so only the most essential connections can be sustained by the fungus. What is the shortest total distance that the mycorrhizal network needs to spread itself across, while still making sure that every plant is connected to every other one?

This particular network has $416$416 spanning trees, which one is minimal? To add up all their weights is going to take a very long time!

Instead, we’re going to use a procedure called Prim’s Algorithm to find the minimal spanning tree without having to find all the spanning trees. The algorithm was first created by Vojtěch Jarník, a Czech mathematician, in 1930. Both Robert Prim (in 1957) and Edsger Dijkstra (in 1959) independently rediscovered it, though Prim’s work popularised its use.

Begin by picking a vertex, any vertex will do. Picking $F$F, highlight the lowest weight edge coming out of $F$F:

Add this edge, and the vertex on the other side, to our spanning tree:

Do the same thing again! Highlight the edge of lowest weight coming out of our spanning tree:

The vertex $F$F was just a starting point - the lowest weight edge connected to the spanning tree comes out of E, now.

Add that edge, and its vertex, to the spanning tree:

The vertex $F$F was just a starting point - the lowest weight edge connected to the spanning tree comes out of E, now.

Once again, highlight the lowest weight edge coming out of the spanning tree:

This time, there are two candidates! Both $DC$DC and $DF$DF have weight $12$12 so pick either one at this point:

The lowest weight edge coming out of the spanning tree is still the weight $12$12 edge $DF$DF:

However, reject this edge, since adding it to our spanning tree would create a cycle, and trees can’t have cycles.

Edges connecting vertices already in the spanning tree will always be rejected.

Now don't consider the edge $DF$DF again and move on to highlighting the next lowest weight edge:

This edge doesn’t create a cycle, so add it in to the growing spanning tree:

The next lowest weight edges are all weight $14$14 so highlight them all:

Once again, reject the edge $DB$DB since it would create a cycle:

That leaves two choices:

Pick either of these and add the edge and the vertex, growing the spanning tree by one vertex every step:

Instead of going back to the edge $EG$EG of weight $14$14, now there is an edge connected to our spanning tree of lower weight:

Add that as before, and highlight the lowest weight edge connecting the spanning tree to our final vertex:

Add this edge and vertex in to the network, completing the procedure:

Delete the unused edges for a clearer picture of our final result:

Our fungus spanning tree has grown from the vertex $F$F to cover every plant in the area, and it covers $12+10+10+13+14+8+7=74$12+10+10+13+14+8+7=74 metres in total.

This procedure is guaranteed to find a minimal spanning tree every time. Much easier than finding all the spanning trees and adding up all their weights!

Prim’s algorithm:

Pick any vertex to start the spanning tree.
Locate the lowest weight edge connected to the spanning tree.
If this edge would create a cycle, reject it.
If there is more than one edge with the lowest weight, pick any of them.
Add this edge and the vertex at the other end to the spanning tree. If all vertices are part of the spanning tree, stop. Otherwise, repeat from step 2.

Practice questions

Question 2

Consider the given weighted network to the right. Which of the following networks is the minimal spanning tree?

A
B
C
D

Question 3

The rangers of a national park want to clear walking tracks to $6$6 landmarks in the area. The potential tracks between landmarks are shown in the graph below, along with the number of days required to clear each track for use.

To make a network of tracks in the shortest time, the rangers want to find a minimal spanning tree for the graph.

Which two of the following are possible minimal spanning trees?
A
B
C
D
What is the minimum time taken to build a network of tracks that connect each landmark?