Loading [MathJax]/jax/element/mml/optable/Latin1Supplement.js

User interface language: English | Español

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.

[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 2e=kf.

[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×72(7+6+5+4+3+2+1)  (a complete graph)        (M1)

=28        A1

[2 marks]

a.ii.

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

=24        A1

[2 marks]

a.iii.

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]

b.i.

using ve+f=2 with v=9       M1

EITHER

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

OR

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

THEN

18f=4

f=14       A1

[3 marks]

b.ii.

2vkf+2f=4  (or equivalent)       M1

when v=13

(k2)f=22  or  (2k)f=22       A1

EITHER

(k2)f=1×2×11      M1

OR

substituting at least two of  k=1343  into  f=22k2  (or equivalent)      M1

THEN

f=211, 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