In the context of graph theory, explain briefly what is meant by a circuit;

In the context of graph theory, explain briefly what is meant by an Eulerian circuit.

The graph $G$ has six vertices and an Eulerian circuit. Determine whether or not its complement $G'$ can have an Eulerian circuit.

Find an example of a graph $H$, with five vertices, such that $H$ and its complement $H'$ both have an Eulerian trail but neither has an Eulerian circuit. Draw $H$ and $H'$ as your solution.

a circuit is a walk that begins and ends at the same vertex and has no repeated edges     A1

[1 mark]

an Eulerian circuit is a circuit that contains every edge of a graph     A1

[1 mark]

if $G$ has an Eulerian circuit all vertices are even (are of degree 2 or 4)     A1

hence, $G'$ must have all vertices odd (of degree 1 or 3)     R1

hence, $G'$ cannot have an Eulerian circuit     R1

Note:     Award A1 to candidates who begin by considering a specific $G$ and $G'$ (diagram). Award R1R1 to candidates who then consider a general $G$ and $G'$.

[3 marks]

for example

A2

A2

Notes:     Each graph must have 3 vertices of order 2 and 2 odd vertices. Award A2 if one of the graphs satisfies that and the final A2 if the other graph is its complement.

[4 marks]