## Question

The graph *G *has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}

{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\

\hline

{\text{A}}& {\text{ – }}&9&{\text{ – }}&8&4 \\

{\text{B}}& 9&{\text{ – }}&7&{\text{ – }}&2 \\

{\text{C}}& {\text{ – }}&7&{\text{ – }}&7&3 \\

{\text{D}}& 8&{\text{ – }}&7&{\text{ – }}&5 \\

{\text{E}}& 4&2&3&5&{\text{ – }}

\end{array}\]

Draw *G *in a planar form.

Giving a reason, determine the maximum number of edges that could be added to *G *while keeping the graph both simple and planar.

List all the distinct Hamiltonian cycles in *G *beginning and ending at A, noting that two cycles each of which is the reverse of the other are to be regarded as identical. Hence determine the Hamiltonian cycle of least weight.

**Answer/Explanation**

## Markscheme

*A2*

*[2 marks]*

For a simple planar graph containing triangles, \(e \leqslant 3v – 6\) *M1*

Here \(v = 5{\text{ , so }}e \leqslant 9\) . *A1*

There are already 8 edges so the maximum number of edges that could be added is 1. *R1*

This can be done *e.g. *AC or BD *R1*

*[4 marks]*

The distinct Hamiltonian cycles are

ABCDEA *A2*

ABCEDA *A2*

ABECDA *A2*

AEBCDA *A2*

**Note: **Do not penalise extra cycles.

The weights are 32, 32, 29, 28 respectively. *A1*

The Hamiltonian cycle of least weight is AEBCDA. *R1*

*[10 marks]*

## Examiners report

A fairly common error in (a) was to draw a non-planar version of *G*, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

A fairly common error in (a) was to draw a non-planar version of *G*, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

A fairly common error in (a) was to draw a non-planar version of *G*, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

## Question

The adjacency table of the graph *G* , with vertices P, Q, R, S, T is given by:

(a) Draw the graph *G* .

(b) (i) Define an Eulerian circuit.

(ii) Write down an Eulerian circuit in *G* starting at P.

(c) (i) Define a Hamiltonian cycle.

(ii) Explain why it is not possible to have a Hamiltonian cycle in *G* .

**Answer/Explanation**

## Markscheme

(a)

*A3*

**Note:** Award ** A2** for one missing or misplaced edge,

** A1** for two missing or misplaced edges.

*[3 marks]*

* *

(b) (i) an Eulerian circuit is one that contains every edge of the graph exactly once *A1*

(ii) a possible Eulerian circuit is

\({\text{P}} \to {\text{Q}} \to {\text{S}} \to {\text{P}} \to {\text{Q}} \to {\text{Q}} \to {\text{R}} \to {\text{T}} \to {\text{R}} \to {\text{R}} \to {\text{P}}\) *A2*

*[3 marks]*

* *

(c) (i) a Hamiltonian cycle passes through each vertex of the graph *A1*

exactly once *A1*

* *

(ii) to pass through T, you must have come from R and must return to R. *R3*

hence there is no Hamiltonian cycle

*[5 marks]*

## Examiners report

Stronger candidates had little problem with this question, but a significant number of weaker candidates started by making errors in drawing the graph G, where the most common error was the omission of the loops and double edges. They also had problems working with the concepts of Eulerian circuits and Hamiltonian cycles.

## Question

The following diagram shows a weighted graph *G *with vertices A, B, C, D and E.

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\).

**Answer/Explanation**

## Markscheme

*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

**is awarded.**

*R1**[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]*

## Examiners report

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).

## Question

The distances by road, in kilometres, between towns in Switzerland are shown in the following table.

A cable television company wishes to connect the six towns placing cables along the road system.

Use Kruskal’s algorithm to find the minimum length of cable needed to connect the six towns.

Visitors to Switzerland can visit some principal locations for tourism by using a network of scenic railways as represented by the following graph:

(i) State whether the graph has any Hamiltonian paths or Hamiltonian cycles, justifying your answers.

(ii) State whether the graph has any Eulerian trails or Eulerian circuits, justifying your answers.

(iii) The tourist board would like to make it possible to arrive in Geneva, travel all the available scenic railways, exactly once, and depart from Zurich. Find which locations would need to be connected by a further scenic railway in order to make this possible.

**Answer/Explanation**

## Markscheme

Zurich-Basel 85 *M1A1*

Berne-Basel 100 *A1*

Sion-Berne 155

Sion-Geneva 160

Zurich-Lugano 210 *A1*

total length of pipe needed is 710 km *A1*

**Note: **Award ** M1 **for attempt to start with smallest length.

**Note: **Accept graphical solution showing lengths chosen.

**Note: **Award ** N1 **for a correct spanning tree and

**for 710 km with no method shown.**

*N1***[6 marks]**

(i) possible Hamiltonian path *eg *Geneva-Montreux-Zermatt-Lugano-St Moritz-Interlaken-Luzern-Zurich-Berne *A1*

no possible Hamiltonian cycles *eg *we would have to pass through Montreux twice as Geneva is only connected to Montreux or Interlaken twice *R1*

(ii) possible Eulerian trail as there are 2 odd vertices (Geneva and St Moritz) *R1*

no possible Eulerian circuits as not all even vertices *R1*

**Note: **Accept an example of a Eulerian trail for the first ** R1**.

(iii) St Moritz to Zurich *A2*

**Note:** If St Moritz and Zurich are connected via existing edges award ** A1**.

**[6 marks]**

**Total [11 marks]**

## Examiners report

[N/A]

[N/A]