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 .

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

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.