(a)     (i)     Show that Euler’s relation \(f - e + v = 2\) is valid for a spanning tree of G.

  (ii)     By considering the effect of adding an edge on the values of  f,  e and v show that Euler’s relation remains true.

(b)     Show that K₅ is not planar.

(a)     (i)     A spanning tree with v vertices and (v −1) edges where f  = 1     A1A1

f − e + v =1 − (v − 1) + v = 2     M1

So the formula is true for the tree     AG

(ii)     Adding one edge connects two different vertices, and hence an extra face is created     M1R1

This leaves v unchanged but increases both e and f by 1 leaving f − e + v unchanged. Hence f − e + v = 2 .     R1R1

[7 marks]

(b)     Using \(e \leqslant 3v - 6\) ,     M1

for \({K_5},{\text{ }}v = 5\) and \(e = \left( {\begin{array}{*{20}{c}}
  5 \\
  2
\end{array}} \right) = 10\)     A1A1

but 3v − 6 = 3(5) − 6 = 9     A1

9 is not greater or equal to 10 so \({K_5}\) is not planar     R1

[5 marks]

Total [12 marks]

Part (a)(i) was done successfully but many students did not read part(ii) carefully. It said ‘adding an edge’ nothing else. Many candidates assumed it was necessary to add a vertex when this was not the case. 

Part (b) was not found to be beyond many candidates if they used the inequality \(e \leqslant 3v - 6\)