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.
Find an expression for e' in terms of e.
Given that the complement of G is also planar and connected, find the possible values of e.
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.
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 e≤3v-6 (M1)
the maximum number of edges is 21 (e≤21) A1
[2 marks]
κ9 has ((92)=) 36 edges (A1)
so e'=36-e (=(92)-e) A1
[2 marks]
e'≤21⇒36-e≤21 (M1)
15≤e≤21 (the possible values are 15, 16, 17, 18, 19, 20 and 21) A1
[2 marks]
recognises that e+e'=v(v-1)2 (or equivalent) (A1)
uses e≤3v-6 and e'≤3v-6 M1
to form v(v-1)2-(3v-6)≤3v-6 A1
Note: Award A1 for v(v-1)2-(3v-6)=3v-6.
attempts to solve their quadratic inequality (equality) (M1)
v2-13v+24≤0⇒2.228…≤v≤10.77…
the maximum possible value of v is 10 (v≤10) A1
[5 marks]