20N.3.AHL.TZ0.HDM_5

pestleMathematicsAIHLPaper 320N· ahl-3-14-graph-theorysource ↗

$G$ is a simple, connected, planar graph with $9$ vertices and $e$ edges.

The complement of $G$ has $e'$ edges.

Find the maximum possible value of $e$ .

[2]

Find an expression for $e'$ in terms of $e$ .

[2]

Given that the complement of $G$ is also planar and connected, find the possible values of $e$ .

[2]

$H$ is a simple graph with $v$ vertices and $e$ edges.

Given that both $H$ and its complement are planar and connected, find the maximum possible value of $v$ .

[5]

Markscheme / solution

* This question is from an exam for a previous syllabus, and may contain minor differences in marking or structure.

substitutes $v = 9$ into either $e = 3 v - 6$ or $e \leq 3 v - 6$ (M1)

the maximum number of edges is $21 (e \leq 21)$ A1

[2 marks]

$κ_{9}$ has $((\begin{matrix} 9 \\ 2 \end{matrix}) =) 36 edges$ (A1)

so $e' = 36 - e (= (\begin{matrix} 9 \\ 2 \end{matrix}) - e)$ A1

[2 marks]

$e' \leq 21 \Rightarrow 36 - e \leq 21$ (M1)

$15 \leq e \leq 21$ (the possible values are $15, 16, 17, 18, 19, 20$ and $21$ ) A1

[2 marks]

recognises that $e + e' = \frac{v (v - 1)}{2}$ (or equivalent) (A1)

uses $e \leq 3 v - 6$ and $e' \leq 3 v - 6$ M1

to form $\frac{v (v - 1)}{2} - (3 v - 6) \leq 3 v - 6$ A1

Note: Award A1 for $\frac{v (v - 1)}{2} - (3 v - 6) = 3 v - 6$ .

attempts to solve their quadratic inequality (equality) (M1)

$v^{2} - 13 v + 24 \leq 0 \Rightarrow 2.228 \dots \leq v \leq 10.77 \dots$

the maximum possible value of $v$ is $10 (v \leq 10)$ A1

[5 marks]

Examiners’ report

[N/A]