(a)     Show that, for a connected planar graph,

$$v + f - e = 2.$$

(b)     Assuming that $v \geqslant 3$, explain why, for a simple connected planar graph, $3f \leqslant 2e$ and hence deduce that $e \leqslant 3v - 6$.

(c)     The graph G and its complement ${G'}$ are simple connected graphs, each having 12 vertices. Show that ${G}$ and ${G'}$ cannot both be planar.

(a)     start with a graph consisting of just a single vertex     M1

for this graph, v = 1, f = 1 and e = 0, the relation is satisfied     A1

Note: Allow solutions that begin with 2 vertices and 1 edge.

to extend the graph you either join an existing vertex to another existing vertex which increases e by 1 and f by 1 so that v + f – e remains equal to 2     M1A1

or add a new vertex and a corresponding edge which increases e by 1 and v by 1 so that v + f – e remains equal to 2     M1A1

therefore, however we build up the graph, the relation remains valid     R1

[7 marks]

(b)     since every face is bounded by at least 3 edges, the result follows by counting up the edges around each face     R1

the factor 2 follows from the fact that every edge bounds (at most) 2 faces     R1

hence $3f \leqslant 2e$     AG

from the Euler relation, $3f = 6 + 3e - 3v$     M1

substitute in the inequality, $6 + 3e - 3v \leqslant 2e$     A1

hence $e \leqslant 3v - 6$     AG

[4 marks]

(c)     let G have e edges     M1

since G and ${G'}$ have a total of $\left( {\begin{array}{*{20}{c}}   {12} \\   2 \end{array}} \right) = 66$ edges     A1

it follows that ${G'}$ has 66 – e edges     A1

for planarity we require

$e \leqslant 3 \times 12 - 6 = 30$     M1A1

and $66 - e \leqslant 30 \Rightarrow e \geqslant 36$     A1

these two inequalities cannot both be met indicating that both graphs cannot be planar     R1

[7 marks]

Total [18 marks]

Parts (a) and (b) were found difficult by many candidates with explanations often inadequate. In (c), candidates who realised that the union of a graph with its complement results in a complete graph were often successful.