Show that the number of edges in $G'$, the complement of $G$, is $\frac{1}{2}{v^2} - \frac{1}{2}v - e$.

show that the sum of the number of faces in $G$ and the number of faces in $G'$ is independent of $e$;

show that ${v^2} - 13v + 24 \leqslant 0$ and hence determine the maximum possible value of $v$.

the total number of edges in $G$ and $G'$ is $\frac{{v(v - 1)}}{2}$     (A1)

the number of edges in $G' = \frac{{v(v - 1)}}{2} - e$     A1

$= \frac{1}{2}{v^2} - \frac{1}{2}v - e$    AG

[2 marks]

using Euler’s formula, number of faces in $G = e + 2 - v$     A1

number of faces in $G' = \frac{{{v^2}}}{2} - \frac{v}{2} - e + 2 - v$     A1

sum of these numbers $= \frac{{{v^2}}}{2} - \frac{{5v}}{2} + 4$     A1

this is independent of $e$     AG

[3 marks]

for $G$ to be planar, we require     (M1)

$e \leqslant 3v - 6$    A1

for $e \leqslant 3v - 6$ to be planar, we require

$\frac{{{v^2}}}{2} - \frac{v}{2} - e \leqslant 3v - 6$    A1

for these two inequalities to be satisfied simultaneously, adding or substituting we require

$\frac{{{v^2}}}{2} - \frac{v}{2} \leqslant 6v - 12$    (M1)A1

leading to ${v^2} - 13v + 24 \leqslant 0$     AG

the roots of the equation are 10.8 (and 2.23)     (A1)

the largest value of $v$ is therefore 10     A1

[7 marks]

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(a) If they considered the complete graph they were fine.

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(b) Some confusion here if they were not clear about which graph they were applying Euler’s formula to. If they were methodical with good notation they obtained the answer.

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(c) Again the same confusion about applying the inequality to both graphs. Most candidates realised which inequality was applicable. Many candidates had the good exam technique to pick up the last two marks even if they did not obtain the quadratic inequality.