User interface language: English | Español

Date November 2020 Marks available 2 Reference code 20N.3.AHL.TZ0.Hdm_5
Level Additional Higher Level Paper Paper 3 Time zone Time zone 0
Command term Find Question number Hdm_5 Adapted from N/A

Question

G is a simple, connected, planar graph with 9 vertices and e edges.

The complement of G has e' edges.

Find the maximum possible value of e.

[2]
a.

Find an expression for e' in terms of e.

[2]
b.

Given that the complement of G is also planar and connected, find the possible values of e.

[2]
c.

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.

[5]
d.

Markscheme

* This question is from an exam for a previous syllabus, and may contain minor differences in marking or structure.

substitutes  v=9  into either  e=3v-6  or  e3v-6        (M1)

the maximum number of edges is  21  e21        A1


[2 marks]

a.

κ9 has 92= 36 edges        (A1)

so  e'=36-e=92-e        A1


[2 marks]

b.

e'2136-e21        (M1)

15e21  (the possible values are 15, 16, 17, 18, 19, 20 and 21)        A1


[2 marks]

c.

recognises that e+e'=vv-12 (or equivalent)        (A1)

uses  e3v-6  and  e'3v-6        M1

to form vv-12-3v-63v-6        A1


Note: Award A1 for vv-12-3v-6=3v-6.


attempts to solve their quadratic inequality (equality)        (M1)

v2-13v+2402.228v10.77

the maximum possible value of v is 10  v10        A1


[5 marks]

d.

Examiners report

[N/A]
a.
[N/A]
b.
[N/A]
c.
[N/A]
d.

Syllabus sections

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

View options