| 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
