Marks available | 2 |

Reference code | 15M.1.hl.TZ0.4 |

## Question

A simple graph \(G\) is represented by the following adjacency table.

Draw the simple graph \(G\).

Explain why \(G\) does not contain an Eulerian circuit.

Show that \(G\) has a Hamiltonian cycle.

State whether or not \(G\) is planar, giving a reason for your answer.

State whether or not the simple graph \(G\) is bipartite, giving a reason for your answer.

Draw the complement \(G’\) of \(G\).

## Markscheme

*A1*

because it has vertices which are not of even degree. *A1*

for example \({\text{D}} \to {\text{C}} \to {\text{B}} \to {\text{E}} \to {\text{A}} \to {\text{F}} \to {\text{D}}\) *A2*

\(G\) is planar. *A1*

either note from original graph in part (a) that there are no edges crossing or a redrawing with statement that there are no edges crossing. *R1*

**Note: **Do not accept an argument based on \(e \leqslant 3v – 6\)

the graph is not bipartite. *A1*

**EITHER**

the graph contains a triangle *R1*

**OR**

to be bipartite according to line 1 of the table A, C and D need to be one set as A connects to B, E and F. Since C and D are connected, this is contradicted. *R1*

*A2*

**Note: **Award ** A1 **if extra line seen or missed out.

## Examiners report

This question was very well answered in general.

This question was very well answered in general.

This question was very well answered in general.

This question was very well answered in general. In (d), some candidates stated that G is planar because \(e \leqslant 3v – 6\). It is however important to realise that this condition is necessary for a graph to be planar but not sufficient. Some candidates stated that G is planar ‘because I have drawn it as a planar graph’ or even ‘see graph in (a)’. Candidates were expected to state that G is planar because it can be drawn with no edges crossing.

This question was very well answered in general.

This question was very well answered in general.

Marks available | 3 |

Reference code | 17M.1.hl.TZ0.11 |

## Question

The simple connected planar graph \(J\) has the following adjacency table.

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.

## Markscheme

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]*