Without attempting to draw \(J\), verify that J satisfies the handshaking lemma;

Without attempting to draw \(J\), determine the number of faces in \(J\).

The vertices D and G are joined by a single edge to form the graph \(K\). Show that \(K\) is not planar.

Explain why a graph containing a cycle of length three cannot be bipartite. 

Hence by finding a cycle of length three, show that the complement of \(K\) is not bipartite.

the sum of degrees of the vertices is even (36) or the sum of degrees of the vertices is twice the number of edges A1

[2 marks]

the number of edges \((e)\) is 18     A1

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

\(f = 2 + 18 - 8 = 12\)     A1

[2 marks]

if \(K\) is planar then \(e \leqslant 3v - 6\)     M1

\(v = 8\) and \(e = 19\)     A1

the inequality is not satisfied so \(K\) is not planar     A1AG

[3 marks]

let PQRP be a cycle of length 3 in a graph     M1

Note:     Accept a diagram instead of this statement.

suppose the graph is bipartite

then P must belong to one of the two disjoint sets of vertices and Q, R must belong to the other disjoint set     R1

but Q, R cannot belong to the same set because they are linked     R1

therefore the graph cannot be bipartite     AG

[??? marks]

for example, a suitable cycle of order 3 is AFHA     (M1)A1

Note:     Award M1 for a valid attempt at drawing the complement or constructing its adjacency table.

[??? marks]