| Date | November 2009 | Marks available | 5 | Reference code | 09N.3dm.hl.TZ0.3 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Show that | Question number | 3 | Adapted from | N/A |
Question
The planar graph G and its complement \(G'\) are both simple and connected.
Given that G has 6 vertices and 10 edges, show that \(G'\) is a tree.
Markscheme
the complete graph with 6 vertices has 15 edges so \(G'\) has
6 vertices and 5 edges M1A1
the number of faces in \(G'\) , \(f = 2 + e - v = 1\) M1A1
it is therefore a tree because \(f = 1\) R1
Note: Accept it is a tree because \(v = e + 1\)
[5 marks]
Examiners report
Part (a) was well answered by many candidates.
Syllabus sections
Topic 10 - Option: Discrete mathematics » 10.7 » Simple graphs; connected graphs; complete graphs; bipartite graphs; planar graphs; trees; weighted graphs, including tabular representation.
Show 23 related questions
