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 A1
[2 marks]
(M1)
(the possible values are and ) A1
[2 marks]
recognises that (or equivalent) (A1)
uses and M1
to form A1
Note: Award A1 for .
attempts to solve their quadratic inequality (equality) (M1)
the maximum possible value of is A1
[5 marks]