Draw the complete bipartite graph \({\kappa _{3,3}}\).

Prove that \({\kappa _{3,3}}\) is not planar.

A connected graph \(G\) has \(v\) vertices. Prove, using Euler’s relation, that a spanning tree for \(G\) has \(v - 1\) edges.

If an edge \(E\) is chosen at random from the edges of \({\kappa _n}\), show that the probability that \(E\) belongs to \(T\) is equal to \(\frac{2}{n}\).

     A1

[1 mark]

assume \({\kappa _{3,3}}\) is planar

\({\kappa _{3,3}}\) has no cycles of length 3     R1

use of \(e \leqslant 2v - 4\)     M1

\(e = 9\) and \(v = 6\)     A1

hence inequality not satisfied 9 \(\not  \leqslant \) 8     R1

so \({\kappa _{3,3}}\) is not planar     AG

Note:     use of \(e \leqslant 3v - 6\) with \(e = 9\) and \(v = 6\) and concluding that this inequality does not show whether \({\kappa _{3,3}}\) is planar or not just gains R1.

[4 marks]

a spanning tree (is planar and) has one face     A1

Euler’s relation is \(v - e + f = 2\)

\(v - e + 1 = 2\)     M1

\( \Rightarrow e = v - 1\)     AG

[2 marks]

\({\kappa _n}\) has \(\left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right)\) edges \(\left( {\frac{{n(n - 1)}}{2}{\text{ edges}}} \right)\)     (A1)

\({\text{P}}(E{\text{ belongs to }}T) = \frac{{n - 1}}{{\left( {\frac{{n(n - 1)}}{2}} \right)}}\)     M1A1

clear evidence of simplification of the above expression     M1

\( = \frac{2}{n}\)     AG

[4 marks]