(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.