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.

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] 

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.