IBDP MAI : Topic 3 Geometry and trigonometry - AHL 3.15 Adjacency matrices AI HL Paper 3
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]