The table below shows the distances between towns A, B, C, D and E.

(i)     Draw the graph, in its planar form, that is represented by the table.

(ii)     Write down with reasons whether or not it is possible to find an Eulerian trail in this graph.

(iii)     Solve the Chinese postman problem with reference to this graph if A is to be the starting and finishing point. Write down the walk and determine the length of the walk.

Show that a graph cannot have exactly one vertex of odd degree.

(i)

    A1A1A1

Note: Award A1 for the vertices, A1 for edges and A1 for planar form.

(ii)     It is possible to find an Eulerian trail in this graph since exactly two of the vertices have odd degree     R1

(iii)     B and D are the odd vertices     M1

\(BC + CD = 3 + 2 = 5{\text{ and }}BD = 9,\)     A1

since 5 < 9 , BC and CD must be traversed twice     R1

A possible walk by inspection is ACBDABCDCEA     A1

This gives a total length of

2(2 + 3) + 8 + 9 + 5 + 7 + 10 + 6 = 55 for the walk     A1 

[9 marks]

The sum of all the vertex degrees is twice the number of edges, i.e. an even number.

Hence a graph cannot have exactly one vertex of odd degree.     M1R1

[2 marks]

Drawing the graph usually presented no difficulty. Distinguishing between Eulerian and semi-Eulerian needs attention but this part was usually done successfully.

A simple, clear argument for part (c) was often hidden in mini-essays on graph theory.

Drawing the graph usually presented no difficulty. Distinguishing between Eulerian and semi-Eulerian needs attention but this part was usually done successfully.

A simple, clear argument for part (c) was often hidden in mini-essays on graph theory.