A graph G with vertices A, B, C, D, E has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}
  {}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
  {\text{A}}& - &{12}&{10}&{17}&{19} \\
  {\text{B}}&{12}& - &{13}&{20}&{11} \\
  {\text{C}}&{10}&{13}& - &{16}&{14} \\
  {\text{D}}&{17}&{20}&{16}& - &{15} \\
  {\text{E}}&{19}&{11}&{14}&{15}& -  
\end{array}\]

(a)     (i)     Use Kruskal’s algorithm to find and draw the minimum spanning tree for G.

  (ii)     The graph H is formed from G by removing the vertex D and all the edges connected to D. Draw the minimum spanning tree for H and use it to find a lower bound for the travelling salesman problem for G.

(b)     Show that 80 is an upper bound for this travelling salesman problem.

(a)     (i)     the edges are joined in the order

AC

BE

AB

ED     A2

     A1

Note: Final A1 independent of the previous A2.

(ii)

    A1

the weight of this spanning tree is 33     A1

to find a lower bound for the travelling salesman problem, we add to that the two smallest weights of edges to D, i.e. 15 +16, giving 64     M1A1

[7 marks]

(b)     an upper bound is the weight of any Hamiltonian cycle, e.g. ABCDEA has weight 75 so 80 is certainly an upper bound     M1A1

[2 marks]

Total [9 marks]

Part (a) was well done by many candidates although some candidates simply drew the minimum spanning tree in (i) without indicating the use of Kruskal’s Algorithm. It is important to stress to candidates that, as indicated in the rubric at the top of Page 2, answers must be supported by working and/or explanations. Part (b) caused problems for some candidates who obtained the unhelpful upper bound of 96 by doubling the weight of the minimum spanning tree. It is useful to note that the weight of any Hamiltonian cycle is an upper bound and in this case it was fairly easy to find such a cycle with weight less than or equal to 80.