Date | November 2019 | Marks available | 4 | Reference code | 19N.3.AHL.TZ0.Hdm_4 |
Level | Additional Higher Level | Paper | Paper 3 | Time zone | Time zone 0 |
Command term | Find | Question number | Hdm_4 | Adapted from | N/A |
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.
Write down the minimum number of edges in G.
Find the maximum number of edges in G.
Find the maximum number of edges in G, given that G contains an Eulerian circuit.
Explain why 2e=kf.
Find the value of f when v=9 and k=3.
Find the possible values of f when v=13.
Markscheme
7 (a tree) A1
[1 mark]
8×72(7+6+5+4+3+2+1) (a complete graph) (M1)
=28 A1
[2 marks]
8×62 (since every vertex must be of degree 6) (M1)
=24 A1
[2 marks]
counting the edges around every face gives kf edges A1
but as every edge is counted in 2 faces R1
⇒kf=2e AG
[2 marks]
using v−e+f=2 with v=9 M1
EITHER
substituting 2e=3f into 2(9)−2e+2f=4 (M1)
OR
substituting e=3f2 into 9−e+f=2 (M1)
THEN
18−f=4
f=14 A1
[3 marks]
2v−kf+2f=4 (or equivalent) M1
when v=13
(k−2)f=22 or (2−k)f=−22 A1
EITHER
(k−2)f=1×2×11 M1
OR
substituting at least two of k=13, 4, 3 into f=22k−2 (or equivalent) M1
THEN
f=2, 11, 22 (since f>1) A1
[4 marks]