Show that graph \(G\) is Hamiltonian. Find the total number of Hamiltonian cycles in \(G\), giving reasons for your answer.

State an upper bound for the travelling salesman problem for graph \(G\).

Hence find a lower bound for the travelling salesman problem for \(G\).

Show that the lower bound found in (d) cannot be the length of an optimal solution for the travelling salesman problem for the graph \(G\).

eg the cycle \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}\) is Hamiltonian     A1

starting from any vertex there are four choices

from the next vertex there are three choices, etc …     R1

so the number of Hamiltonian cycles is \(4!{\text{ }}( = 24)\)     A1

 

Note: Allow 12 distinct cycles (direction not considered) or 60 (if different starting points count as distinct). In any case, just award the second A1 if R1 is awarded.

 

[3 marks]

total weight of any Hamiltonian cycles stated

eg \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{A}}\) has weight \(5 + 6 + 7 + 8 + 9 = 35\)     A1

[1 mark]

a lower bound for the travelling salesman problem is then obtained by adding the weights of CA and CB to the weight of the minimum spanning tree     (M1)

 

a lower bound is then \(14 + 6 + 6 = 26\)     A1

[2 marks]

METHOD 1

eg eliminating A from G, a minimum spanning tree of weight 18 is     (M1)

     A1

adding AD and AB to the spanning tree gives a lower bound of \(18 + 4 + 5 = 27 > 26\)     A1

so 26 is not the best lower bound     AG

 

Note: Candidates may delete other vertices and the lower bounds obtained are B-28, D-27 and E-28.

 

METHOD 2

there are 12 distinct cycles (ignoring direction) with the following lengths

Cycle     Length

ABCDEA     35     M1

ABCEDA     33

ABDCEA     39

ABDECA     37

ABECDA     31

ABEDCA     31

ACBDEA     37

ACBEDA     29

ACDBEA     35

ACEBDA     33

AEBCDA     31

AECBDA     37     A1

as the optimal solution has length 29     A1

26 is not the best possible lower bound     AG

 

Note: Allow answers where candidates list the 24 cycles obtained by allowing both directions.

 

[3 marks]

Part (a) was generally well answered, with a variety of interpretations accepted.

Part (b) also had a number of acceptable possibilities.

Part (d) was generally well answered, but there were few good attempts at part (e).

Part (d) was generally well answered, but there were few good attempts at part (e).