| Date | May 2010 | Marks available | 18 | Reference code | 10M.3dm.hl.TZ0.4 |
| Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
| Command term | Deduce, Explain, Hence, and Show that | Question number | 4 | Adapted from | N/A |
Question
(a) Show that, for a connected planar graph,
\[v + f - e = 2.\]
(b) Assuming that \(v \geqslant 3\), explain why, for a simple connected planar graph, \(3f \leqslant 2e\) and hence deduce that \(e \leqslant 3v - 6\).
(c) The graph G and its complement \({G'}\) are simple connected graphs, each having 12 vertices. Show that \({G}\) and \({G'}\) cannot both be planar.
Markscheme
(a) start with a graph consisting of just a single vertex M1
for this graph, v = 1, f = 1 and e = 0, the relation is satisfied A1
Note: Allow solutions that begin with 2 vertices and 1 edge.
to extend the graph you either join an existing vertex to another existing vertex which increases e by 1 and f by 1 so that v + f – e remains equal to 2 M1A1
or add a new vertex and a corresponding edge which increases e by 1 and v by 1 so that v + f – e remains equal to 2 M1A1
therefore, however we build up the graph, the relation remains valid R1
[7 marks]
(b) since every face is bounded by at least 3 edges, the result follows by counting up the edges around each face R1
the factor 2 follows from the fact that every edge bounds (at most) 2 faces R1
hence \(3f \leqslant 2e\) AG
from the Euler relation, \(3f = 6 + 3e - 3v\) M1
substitute in the inequality, \(6 + 3e - 3v \leqslant 2e\) A1
hence \(e \leqslant 3v - 6\) AG
[4 marks]
(c) let G have e edges M1
since G and \({G'}\) have a total of \(\left( {\begin{array}{*{20}{c}}
{12} \\
2
\end{array}} \right) = 66\) edges A1
it follows that \({G'}\) has 66 – e edges A1
for planarity we require
\(e \leqslant 3 \times 12 - 6 = 30\) M1A1
and \(66 - e \leqslant 30 \Rightarrow e \geqslant 36\) A1
these two inequalities cannot both be met indicating that both graphs cannot be planar R1
[7 marks]
Total [18 marks]
Examiners report
Parts (a) and (b) were found difficult by many candidates with explanations often inadequate. In (c), candidates who realised that the union of a graph with its complement results in a complete graph were often successful.
