User interface language: English | Español

Date November 2019 Marks available 3 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 .

[1]
a.i.

Find the maximum number of edges in G .

[2]
a.ii.

Find the maximum number of edges in G , given that G contains an Eulerian circuit.

[2]
a.iii.

Explain why 2 e = k f .

[2]
b.i.

Find the value of f when v = 9 and k = 3 .

[3]
b.ii.

Find the possible values of f when v = 13 .

[4]
b.iii.

Markscheme

7 (a tree)        A1

[1 mark]

a.i.

8 × 7 2 ( 7 + 6 + 5 + 4 + 3 + 2 + 1 )   (a complete graph)        (M1)

= 28         A1

[2 marks]

a.ii.

8 × 6 2 (since every vertex must be of degree 6)        (M1)

= 24         A1

[2 marks]

a.iii.

counting the edges around every face gives k f edges       A1

but as every edge is counted in 2 faces        R1

k f = 2 e        AG

[2 marks]

b.i.

using  v e + f = 2 with  v = 9        M1

EITHER

substituting  2 e = 3 f   into  2 ( 9 ) 2 e + 2 f = 4        (M1)

OR

substituting  e = 3 f 2   into  9 e + f = 2        (M1)

THEN

18 f = 4

f = 14        A1

[3 marks]

b.ii.

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 × 2 × 11       M1

OR

substituting at least two of  k = 13 4 3   into   f = 22 k 2   (or equivalent)      M1

THEN

f = 2 11 , 22   (since  f > 1 )       A1

[4 marks]

b.iii.

Examiners report

[N/A]
a.i.
[N/A]
a.ii.
[N/A]
a.iii.
[N/A]
b.i.
[N/A]
b.ii.
[N/A]
b.iii.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.14—Graph theory
Show 27 related questions
Topic 3—Geometry and trigonometry

View options