| Date | May 2011 | Marks available | 4 | Reference code | 11M.3dm.hl.TZ0.4 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Determine | Question number | 4 | Adapted from | N/A |
Question
The diagram below shows the graph G with vertices A, B, C, D, E and F.
(i) Determine if any Hamiltonian cycles exist in G . If so, write one down.
Otherwise, explain what feature of G makes it impossible for a Hamiltonian cycle to exist.
(ii) Determine if any Eulerian circuits exist in G . If so, write one down.
Otherwise, explain what feature of G makes it impossible for an Eulerian circuit to exist.
Markscheme
(i) any Hamiltonian circuit ACBEFDA A2
(ii) no Eulerian circuit exists because the graph contains vertices of odd degree A2
[4 marks]
Examiners report
Parts (a) and (b) were well answered by many candidates. In (c), candidates who tried to prove the result by adding edges to a drawing of G were given no credit. Candidates should be aware that the use of the word ‘Prove’ indicates that a formal treatment is required Solutions to (d) were often disappointing although a graphical solution was allowed here.
