| Date | May 2008 | Marks available | 4 | Reference code | 08M.3dm.hl.TZ1.4 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ1 |
| Command term | Determine | Question number | 4 | Adapted from | N/A |
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.
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.
