State what feature of G ensures that G has an Eulerian trail.

State what feature of G ensures that G does not have an Eulerian circuit.

Write down an Eulerian trail in G.

State the Chinese postman problem.

Starting and finishing at B, find a solution to the Chinese postman problem for G.

Calculate the total weight of the solution.

G has an Eulerian trail because it has (exactly) two vertices (B and F) of odd degree      R1

[1 mark]

G does not have an Eulerian circuit because not all vertices are of even degree      R1

[1 mark]

for example BAEBCEFCDF      A1A1

Note: Award A1 for start/finish at B/F, A1 for the middle vertices.

[2 marks]

to determine the shortest route (walk) around a weighted graph      A1

using each edge (at least once, returning to the starting vertex)      A1

Note: Correct terminology must be seen. Do not accept trail, path, cycle or circuit.

[2 marks]

we require the Eulerian trail in (b), (weight = 65)     (M1)

and the minimum walk FEB (15)     A1

for example BAEBCEFCDFEB    A1

Note: Accept EB added to the end or FE added to the start of their answer in (b) in particular for follow through.

[3 marks]

total weight is (65 + 15=)80      A1

[1 mark]