Which of these networks is a tree?
A
B
C
Why is the following network not a tree?

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

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

Question 2

Sarah has three children: Kate, Matt and Tom. Kate has four children, Lisa, Sandy, Amy and Robert, and Matt has two sons, Joseph and Chris. Both Tom and Lisa have one child each: Barbara and Alex, respectively.

If the starting vertex represents Sarah, create a tree to represent the parent-child relationships in this family.

Spanning trees

A spanning tree is a subnetwork of a connected network that is also a tree. It has no cycles or loops.

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.

Practice question

Question 3

Does the following network have a spanning tree?

Yes
A
No
B

A connected network that isn’t already a tree can have multiple spanning trees. The network below has $11$11 possible spanning trees:

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

Here are all the spanning trees, with their weights. Notice that all the spanning trees have the same number of edges. The spanning tree for a network with $n$n vertices will have $(n-1)$(n−1) edges.

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 in the previous example 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? It can be quite hard and take a long time. In following lesson we will investigate a more systematic way to find a minimal spanning tree.