9.05 Spanning trees

A connected network where there is only one possible path between any two vertices is called a tree. These types of networks have a distinctly tree-like appearance:

We can take any connected network and remove edges and vertices to create subnetworks that are trees, like in this example:

The subnetwork in the bottom right has the same number of vertices as the original network, and is also a tree. We give this kind of subnetwork a special name - it is called a spanning tree, because it is a tree that spans all vertices! Here are all the different spanning trees we can find from the original network:

Notice that all of a spanning tree's edges are necessary to keep it connected. If any edge were removed from any of them the network would become disconnected. Also notice that the original network has four vertices, and every spanning tree has three edges - a spanning tree always has one less edge than the number of vertices in the original.

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

… 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

Minimal spanning trees

The last spanning tree is special, because it has the lowest weight out of all of them. We call it 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?

Practice questions

Question 1

Question 2