Show that \(G\) is bipartite.

State which two vertices should be joined to make \(G\) equivalent to \({K_{3,{\text{ }}3}}\).

In a planar graph the degree of a face is defined as the number of edges adjacent to that face.

(i)     Write down the degree of each of the four faces of \(G\).

(ii)     Explain why the sum of the degrees of all the faces is twice the number of edges.

\(H\) is a simple connected planar bipartite graph with \(e\) edges, \(f\) faces, \(v\) vertices and \(v \ge 3\).

Explain why there can be no face in \(H\) of degree

(i)     one;

(ii)     two;

(iii)     three.

Hence prove that for \(H\)

(i)     \(e \ge 2f\);

(ii)     \(e \le 2v - 4\).

Hence prove that \({K_{3,{\text{ }}3}}\) is not planar.

shading alternate vertices or attempting to list pairs     M1

EITHER

     A1

OR

\(ADE\) and \(BCF\)     A1

as no two equal shadings are adjacent, the graph is bipartite     AG

[2 marks]

\(C\) and \(E\)     A1

[1 mark]

(i)     degree of each of the four faces is \(4\)     A1

(ii)     each edge bounds two faces     R1

[2 marks]

(i)     simple so no loops     R1

(ii)     simple so no multiple edges (and \(v > 2\))     R1

(iii)     bipartite graph so no triangles     R1

[3 marks]

(i)     \(2e = \sum {\deg (f) \ge 4f} \)     R1

\(e \ge 2f\)     AG

(ii)     if \(H\) is a simple connected planar graph then \(e + 2 = v + f\)     M1

\(e + 2 - v \le \frac{1}{2}e\)     M1

\(2e + 4 - 2v \le e\)

\(e \le 2v - 4\)     AG

[3 marks]

for \({K_{3,{\text{ }}3}}{\text{ }}v = 6\), and \(e = 9\)     A1

\(9 \le 2 \times 6 - 4\) is not true, therefore \({K_{3,{\text{ }}3}}\) cannot be planar     R1AG

[2 marks]

Total [13 marks]