The weighted graph H is shown below.

Use Kruskal’s Algorithm, indicating the order in which the edges are added, to find and draw the minimum spanning tree for H.

(i)     A tree has v vertices. State the number of edges in the tree, justifying your answer.

(ii)     We will call a graph with v vertices a “forest” if it consists of c components each of which is a tree. 

Here is an example of a forest with 4 components.

How many edges will a forest with v vertices and c components have?

The edges are included in the order

CF     A1

EF     A1

BC     A1

CD     A1

AB     A1

     A1

[6 marks]

(i)     A tree with v vertices has v −1 edges.     A1

Using v + f = e + 2 with f = 1, the result follows.     R1

(ii)     Each of the c trees will have one less edge than the number of vertices.     R1

Thus the forest will have v − c edges.     A2

[5 marks]

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result. 

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result.