# IB DP Maths Topic 10.8 Hamiltonian paths and cycles. HL Paper 3

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


a.

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


b.

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.


c.

## Markscheme A2

[2 marks]

a.

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]

b.

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]

c.

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

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.

b.

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.

c.

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

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


a.

State an upper bound for the travelling salesman problem for graph $$G$$.


b.

Hence find a lower bound for the travelling salesman problem for $$G$$.


d.

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


e.

## 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 R1 is awarded.

[3 marks]

a.

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]

b.

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]

d.

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]

e.

## Examiners report

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

a.

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

b.

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

d.

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

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.


a.

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.


b.

## 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:     Accept graphical solution showing lengths chosen.

Note:     Award N1 for a correct spanning tree and N1 for 710 km with no method shown.

[6 marks]

a.

(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]

b.

[N/A]

a.

[N/A]

b.