(i)     A graph is simple, planar and connected. Write down the inequality connecting v and e, and give the condition on v for this inequality to hold.

(ii)     Sketch a simple, connected, planar graph with v = 2 where the inequality from part (b)(i) is not true.

(iii)     Sketch a simple, connected, planar graph with v =1 where the inequality from part (b)(i) is not true.

(iv)     Given a connected, planar graph with v vertices, ${v^2}$ edges and 8 faces, find v. Sketch a graph that fulfils all of these conditions.

(i)     $e \leqslant 3v - 6,{\text{ for }}v \geqslant 3$     A1A1

(ii)         A1

(iii)         A1

(iv)     from Euler’s relation $v - e + f = 2$

$v - {v^2} + 8 = 2$     M1

${v^2} - v - 6 = 0$     A1

$(v + 2)(v - 3) = 0$

$v = 3$     A1

for example

    A1

Note: There are many possible graphs.

[8 marks]

In (b) most candidates gave the required inequality although some just wrote down both inequalities from their formula booklet. The condition $v \geqslant 3$ was less well known but could be deduced from the next 2 graphs. Euler’s relation was used well to obtain the quadratic to solve and many candidates could then draw a correct graph.