Draw ${K_{2,{\text{ }}2}}$ as a planar graph.

Draw a spanning tree for ${K_{2,{\text{ }}2}}$.

Draw the graph of the complement of ${K_{2,{\text{ }}2}}$.

Show that the complement of any complete bipartite graph does not possess a spanning tree.

     A1A1

Note:     Award A1 for a correct version of ${K_{2,{\text{ }}2}}$ and A1 for a correct planar representation.

[2 marks]

     A1

[1 mark]

     A1

[1 mark]

the complete bipartite graph ${K_{m,{\text{ }}n}}$ has two subsets of vertices $A$ and $B$, such that each element of $A$ is connected to every element of $B$     A1

in the complement, no element of $A$ is connected to any element of $B$. The complement is not a connected graph     A1

by definition a tree is connected     R1

hence the complement of any complete bipartite graph does not possess a spanning tree     AG

[3 marks]

Total [7 marks]

Part (a) was generally well done with a large number of candidates drawing a correct planar representation for ${K_{2,2}}$. Some candidates, however, produced a correct non-planar representation of ${K_{2,2}}$.

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for ${K_{2,2}}$ and the correct complement of ${K_{2,2}}$.

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for ${K_{2,2}}$ and the correct complement of ${K_{2,2}}$.

Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of ${K_{m,n}}$ does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.