(i)     Explain briefly why the graph contains an Eulerian trail but not an Eulerian circuit.

(ii)     Write down an Eulerian trail.

(i)     Use Dijkstra’s algorithm to find the path of minimum total weight joining A to D.

(ii)     State the minimum total weight.

(i)     there is an Eulerian trail because there are only 2 vertices of odd degree     R1

there is no Eulerian circuit because not all vertices have even degree     R1

(ii)     eg GBAGFBCFECDE     A2

[4 marks]

(i)

\(\begin{array}{*{20}{l}}
  {{\text{Step}}}&{{\text{Vertices labelled}}}&{{\text{Working values}}}&{} \\
  1&{\text{A}}&{{\text{A(0), B-3, G-2}}}&{{\boldsymbol{M1A1}}} \\
  2&{{\text{A, G}}}&{{\text{A(0), G(2), B-3, F-8}}}&{{\boldsymbol{A1}}} \\
  3&{{\text{A, G, B}}}&{{\text{A(0), G(2), B(3), F-7, C-10}}}&{{\boldsymbol{A1}}} \\
  4&{{\text{A, G, B, F}}}&{{\text{A(0), G(2), B(3), F(7), C-9, E-12}}}&{} \\
  5&{{\text{A, G, B, F, C}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E-10, D-15}}}&{{\boldsymbol{A1}}} \\
  6&{{\text{A, G, B, F, C, E}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D-14}}}&{} \\
  7&{{\text{A, G, B, F, C, E, D}}}&{{\text{A(0), G(2), B(3), F(7), C(9), E(10), D(14)}}}&{{\boldsymbol{A1}}}
\end{array}\)

Note: In both (i) and (ii) accept the tabular method including back tracking or labels by the vertices on a graph.

Note: Award M1A1A1A1A0A0 if final labels are correct but intermediate ones are not shown.

(ii)     minimum weight path is ABFCED     A1

minimum weight is 14     A1

Note: Award the final two A1 marks whether or not Dijkstra’s Algorithm is used.

[8 marks]

In part (a) the criteria for Eulerian circuits and trails were generally well known and most candidates realised that they must start/finish at G/E. Candidates who could not do (a) generally struggled on the paper.

For part (b) the layout varied greatly from candidate to candidate. Not all candidates made their method clear and some did not show the temporary labels. It is recommended that teachers look at the tabular method with its backtracking system as it is an efficient way of tackling this type of problem and has a very clear layout.