Question
$G$ is a simple, connected graph with eight vertices.
$H$ is a connected, planar graph, with $v$ vertices, $e$ edges and $f$ faces. Every face in $H$ is bounded by exactly $k$ edges.
a.i. Write down the minimum number of edges in $G$.
a.i.Find the maximum number of edges in $G$.
a.iiiFind the maximum number of edges in $G$, given that $G$ contains an Eulerian circuit.
b.i.Explain why $2 e=k f$.
b.iiFind the value of $f$ when $v=9$ and $k=3$.
b.iiiFind the possible values of $f$ when $v=13$
▶️Answer/Explanation
a.i. 7 (a tree)
A1
[1 mark]
a.ii. $\frac{8 \times 7}{2}(7+6+5+4+3+2+1)$ (a complete graph)
(M1)
$=28$
A1
[2 marks]
a.iii $\frac{8 \times 6}{2}$ (since every vertex must be of degree 6 )
(M1)
$=24$
A1
[2 marks]
b.i.counting the edges around every face gives $k f$ edges
A1
but as every edge is counted in 2 faces $\quad \boldsymbol{R} \boldsymbol{1}$
$$
\Rightarrow k f=2 e \quad \text { AG }
$$
[2 marks]
b.ii.using $v-e+f=2$ with $v=9 \quad$ M1
EITHER
substituting $2 e=3 f$ into $2(9)-2 e+2 f=4 \quad$ (M1)
OR
substituting $e=\frac{3 f}{2}$ into $9-e+f=2 \quad$ (M1)
THEN
$$
18-f=4
$$
$f=14$
A1
[3 marks]
b.iii $2 v-k f+2 f=4$ (or equivalent) M1
when $v=13$
$(k-2) f=22$ or $(2-k) f=-22$
A1
EITHER
$$
(k-2) f=1 \times 2 \times 11 \quad \text { M1 }
$$
OR
substituting at least two of $k=13,4,3$ into $f=\frac{22}{k-2}$ (or equivalent) M1
THEN
$f=2,11,22($ since $f>1) \quad$ A1
[4 marks]
Question
$G$ is a simple, connected, planar graph with 9 vertices and $e$ edges.
The complement of $G$ has $e^{\prime}$ edges.
a. Find the maximum possible value of $e$.
b. Find an expression for $e^{\prime}$ in terms of $e$.
c. Given that the complement of $G$ is also planar and connected, find the possible values of $e$.
d. $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$.
▶️Answer/Explanation
a.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) \quad$ A1
[2 marks]
b.
$\kappa_9$ has $\left(\left(\begin{array}{l}9 \\ 2\end{array}\right)=\right) 36$ edges
(A1)
so $e^{\prime}=36-e\left(=\left(\begin{array}{l}9 \\ 2\end{array}\right)-e\right)$
A1
[2 marks]
c. $e^{\prime} \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]
d. recognises that $e+e^{\prime}=\frac{v(v-1)}{2}$ (or equivalent)
(A1)
uses $e \leq 3 v-6$ and $e^{\prime} \leq 3 v-6 \quad$ M1
to form $\frac{v(v-1)}{2}-(3 v-6) \leq 3 v-6$
A1
Note: Award $\boldsymbol{A 1}$ 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 \ldots \leq v \leq 10.77 \ldots
$$
the maximum possible value of $v$ is $10(v \leq 10)$
A1
[5 marks]