Draw the graph G as a planar graph.

Giving a reason, state whether or not G is

(i)     simple;

(ii)     connected;

(iii)     bipartite.

Explain what feature of G enables you to state that it has an Eulerian trail and write down a trail.

Explain what feature of G enables you to state it does not have an Eulerian circuit.

Find the maximum number of edges that can be added to the graph G (not including any loops or further multiple edges) whilst still keeping it planar.

     A2

[2 marks]

(i)     G is not simple because 2 edges join P to T     R1

(ii)     G is connected because there is a path joining every pair of vertices     R1

(iii)     (P, R) and (Q, S, T) are disjoint vertices     R1

so G is bipartite     A1

Note: Award the A1 only if the R1 is awarded.

[4 marks]

G has an Eulerian trail because it has two vertices of odd degree (R and T have degree 3), all the other vertices having even degree     R1

the following example is such a trail

TPTRSPQR     A1

[2 marks]

G has no Eulerian circuit because there are 2 vertices which have odd degree     R1

[1 mark]

consider

so it is possible to add 3 extra edges     A1

consider G with one of the edges PT deleted; this is a simple graph with 6 edges; on addition of the new edges, it will still be simple     M1

\(e \leqslant 3v - 6 \Rightarrow e \leqslant 3 \times 5 - 6 = 9\)     R1

so at most 3 edges can be added     R1

[4 marks]