Date | May 2012 | Marks available | 3 | Reference code | 12M.3dm.hl.TZ0.4 |
Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
Command term | Draw | Question number | 4 | Adapted from | N/A |
Question
Draw the complement of the following graph as a planar graph.
A simple graph G has v vertices and e edges. The complement \(G'\) of G has \({e'}\) edges.
(i) Prove that \(e \leqslant \frac{1}{2}v(v - 1)\) .
(ii) Find an expression for \(e + e'\) in terms of v .
(iii) Given that \({G'}\) is isomorphic to G , prove that v is of the form 4n or 4n + 1 for \(n \in {\mathbb{Z}^ + }\) .
(iv) Prove that there is a unique simple graph with 4 vertices which is isomorphic to its complement.
(v) Prove that if \(v \geqslant 11\) , then G and \({G'}\) cannot both be planar.
Markscheme
as a first step, form the following graph
(M1)(A1)
make it planar
A1
[3 marks]
(i) an edge joins a pair of vertices R1
there is a maximum of \(\left( {\begin{array}{*{20}{c}}
v \\
2
\end{array}} \right) = \frac{1}{2}v(v - 1)\) possible unordered pairs of vertices, hence displayed result A1AG
(ii) an edge joins two vertices in \({G'}\) if it does not join them in G and vice versa; all possible edges are accounted for by the union of the two graphs R1
\(e + e' = \frac{1}{2}v(v - 1)\) A1
(iii) the two graphs have the same number of edges R1
\( \Rightarrow e = \frac{1}{4}v(v - 1)\) A1
v and v – 1 are consecutive integers, so only one can be divisible by 4, hence displayed result A1AG
(iv) the required graphs have four vertices and three edges A1
if one vertex is adjacent to the other three, that uses up the edges; the resulting graph, necessarily connected, has a disconnected complement, and vice versa R1
if one vertex is adjacent to two others, that uses up two edges; the final vertex cannot be adjacent to the first; the result is the linear connected graph A1
state it is isomorphic to its complement A1 N2
Note: Alternative proofs are possible, but should include the final statement for full marks.
(v) using \(e \leqslant 3v - 6\) for planar graphs M1
\(\frac{1}{2}v(v - 1) = e + e' \leqslant 6v - 12\) A1
\({v^2} - 13v + 24 \leqslant 0\) is not possible for \(v \geqslant 11\) R1
[14 marks]
Examiners report
Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.
Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.