# IB DP Maths Topic 10.7 Euler’s relation: v−e+f=2 ; theorems for planar graphs HL Paper 3

## Question

Let G be a simple, connected, planar graph.

(a)     (i)     Show that Euler’s relation $$f – e + v = 2$$ is valid for a spanning tree of G.

(ii)     By considering the effect of adding an edge on the values of  fe and v show that Euler’s relation remains true.

(b)     Show that K5 is not planar.

## Markscheme

(a)     (i)     A spanning tree with v vertices and (v −1) edges where = 1     A1A1

f e + v =1 − (v − 1) + v = 2     M1

So the formula is true for the tree     AG

(ii)     Adding one edge connects two different vertices, and hence an extra face is created     M1R1

This leaves v unchanged but increases both e and f by 1 leaving f e + v unchanged. Hence f e + v = 2 .     R1R1

[7 marks]

(b)     Using $$e \leqslant 3v – 6$$ ,     M1

for $${K_5},{\text{ }}v = 5$$ and $$e = \left( {\begin{array}{*{20}{c}} 5 \\ 2 \end{array}} \right) = 10$$     A1A1

but 3v − 6 = 3(5) − 6 = 9     A1

9 is not greater or equal to 10 so $${K_5}$$ is not planar     R1

[5 marks]

Total [12 marks]

## Examiners report

Part (a)(i) was done successfully but many students did not read part(ii) carefully. It said ‘adding an edge’ nothing else. Many candidates assumed it was necessary to add a vertex when this was not the case.

Part (b) was not found to be beyond many candidates if they used the inequality $$e \leqslant 3v – 6$$

## Question

(a)     Show that, for a connected planar graph,

$v + f – e = 2.$

(b)     Assuming that $$v \geqslant 3$$, explain why, for a simple connected planar graph, $$3f \leqslant 2e$$ and hence deduce that $$e \leqslant 3v – 6$$.

(c)     The graph G and its complement $${G’}$$ are simple connected graphs, each having 12 vertices. Show that $${G}$$ and $${G’}$$ cannot both be planar.

## Markscheme

(a)     start with a graph consisting of just a single vertex     M1

for this graph, v = 1, f = 1 and e = 0, the relation is satisfied     A1

Note: Allow solutions that begin with 2 vertices and 1 edge.

to extend the graph you either join an existing vertex to another existing vertex which increases e by 1 and f by 1 so that v + fe remains equal to 2     M1A1

or add a new vertex and a corresponding edge which increases e by 1 and v by 1 so that v + fe remains equal to 2     M1A1

therefore, however we build up the graph, the relation remains valid     R1

[7 marks]

(b)     since every face is bounded by at least 3 edges, the result follows by counting up the edges around each face     R1

the factor 2 follows from the fact that every edge bounds (at most) 2 faces     R1

hence $$3f \leqslant 2e$$     AG

from the Euler relation, $$3f = 6 + 3e – 3v$$     M1

substitute in the inequality, $$6 + 3e – 3v \leqslant 2e$$     A1

hence $$e \leqslant 3v – 6$$     AG

[4 marks]

(c)     let G have e edges     M1

since G and $${G’}$$ have a total of $$\left( {\begin{array}{*{20}{c}} {12} \\ 2 \end{array}} \right) = 66$$ edges     A1

it follows that $${G’}$$ has 66 – e edges     A1

for planarity we require

$$e \leqslant 3 \times 12 – 6 = 30$$     M1A1

and $$66 – e \leqslant 30 \Rightarrow e \geqslant 36$$     A1

these two inequalities cannot both be met indicating that both graphs cannot be planar     R1

[7 marks]

Total [18 marks]

## Examiners report

Parts (a) and (b) were found difficult by many candidates with explanations often inadequate. In (c), candidates who realised that the union of a graph with its complement results in a complete graph were often successful.

## Question

(i)     A graph is simple, planar and connected. Write down the inequality connecting v and e, and give the condition on v for this inequality to hold.

(ii)     Sketch a simple, connected, planar graph with v = 2 where the inequality from part (b)(i) is not true.

(iii)     Sketch a simple, connected, planar graph with v =1 where the inequality from part (b)(i) is not true.

(iv)     Given a connected, planar graph with v vertices, $${v^2}$$ edges and 8 faces, find v. Sketch a graph that fulfils all of these conditions.

## Markscheme

(i)     $$e \leqslant 3v – 6,{\text{ for }}v \geqslant 3$$     A1A1

(ii)         A1

(iii)         A1

(iv)     from Euler’s relation $$v – e + f = 2$$

$$v – {v^2} + 8 = 2$$     M1

$${v^2} – v – 6 = 0$$     A1

$$(v + 2)(v – 3) = 0$$

$$v = 3$$     A1

for example

A1

Note: There are many possible graphs.

[8 marks]

## Examiners report

In (b) most candidates gave the required inequality although some just wrote down both inequalities from their formula booklet. The condition $$v \geqslant 3$$ was less well known but could be deduced from the next 2 graphs. Euler’s relation was used well to obtain the quadratic to solve and many candidates could then draw a correct graph.

## Question

Draw the complement of the following graph as a planar graph.

[3]
a.

A simple graph G has v vertices and e edges. The complement $$G’$$ of G has $${e’}$$ edges.

(i)     Prove that $$e \leqslant \frac{1}{2}v(v – 1)$$ .

(ii)     Find an expression for $$e + e’$$ in terms of v .

(iii)     Given that $${G’}$$ is isomorphic to G , prove that v is of the form 4n or 4n + 1 for $$n \in {\mathbb{Z}^ + }$$ .

(iv)     Prove that there is a unique simple graph with 4 vertices which is isomorphic to its complement.

(v)     Prove that if $$v \geqslant 11$$ , then G and $${G’}$$ cannot both be planar.

[14]
b.

## Markscheme

as a first step, form the following graph

(M1)(A1)

make it planar

A1

[3 marks]

a.

(i)     an edge joins a pair of vertices     R1

there is a maximum of $$\left( {\begin{array}{*{20}{c}} v \\ 2 \end{array}} \right) = \frac{1}{2}v(v – 1)$$ possible unordered pairs of vertices, hence displayed result     A1AG

(ii)     an edge joins two vertices in $${G’}$$ if it does not join them in G and vice versa; all possible edges are accounted for by the union of the two graphs     R1

$$e + e’ = \frac{1}{2}v(v – 1)$$     A1

(iii)     the two graphs have the same number of edges     R1

$$\Rightarrow e = \frac{1}{4}v(v – 1)$$     A1

v and v – 1 are consecutive integers, so only one can be divisible by 4, hence displayed result     A1AG

(iv)     the required graphs have four vertices and three edges     A1

if one vertex is adjacent to the other three, that uses up the edges; the resulting graph, necessarily connected, has a disconnected complement, and vice versa     R1

if one vertex is adjacent to two others, that uses up two edges; the final vertex cannot be adjacent to the first; the result is the linear connected graph     A1

state it is isomorphic to its complement     A1     N2

Note: Alternative proofs are possible, but should include the final statement for full marks.

(v)     using $$e \leqslant 3v – 6$$ for planar graphs     M1

$$\frac{1}{2}v(v – 1) = e + e’ \leqslant 6v – 12$$     A1

$${v^2} – 13v + 24 \leqslant 0$$ is not possible for $$v \geqslant 11$$     R1

[14 marks]

b.

## Examiners report

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

a.

Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.

b.

## Question

A simple connected planar graph, has $$e$$ edges, $$v$$ vertices and $$f$$ faces.

(i)     Show that $$2e \ge 3f{\text{ if }}v > 2$$.

(ii)     Hence show that $${K_5}$$, the complete graph on five vertices, is not planar.

[6]
a.

(i)     State the handshaking lemma.

(ii)     Determine the value of $$f$$, if each vertex has degree $$2$$.

[4]
b.

Draw an example of a simple connected planar graph on $$6$$ vertices each of degree $$3$$.

[2]
c.

## Markscheme

(i)     METHOD 1

attempting to use $$f = e – v + 2$$ and $$e \le 3v – 6$$ (if $$v > 2$$)     (M1)

$$2e \le 6v – 12 = 6(e – f + 2) – 12$$     M1A1

leading to $$2e \ge 3f$$     AG

METHOD 2

each face is bounded by at least three edges     A1

Note:     Award A1 for stating $$e \ge 3f$$.

each edge either separates two faces or, if an edge is interior to a face, it gets counted twice     R1

Note:     Award R1 for stating that each edge contributes two to the sum of the degrees of the faces (or equivalent) ie, $$\sum {\deg (F) = 2e}$$.

adding up the edges around each face     R1

leading to $$2e \ge 3f$$     AG

(ii)     $${K_5}$$ has $$e = 10$$     A1

if the graph is planar, $$f = 7$$     A1

this contradicts the inequality obtained above     R1

hence the graph is non-planar     AG

[6 marks]

a.

(i)     the sum of the vertex degrees $$= 2e$$ (or is even) or equivalent     A1

(ii)     if each vertex has degree $$2$$, then $$2v = 2e$$     A1

substituting $$v = e$$ into Euler’s formula     M1

$$f = 2$$     A1

[4 marks]

b.

for example,

A2

[2 marks]

Total [12 marks]

c.

## Examiners report

In part (a) (i), many candidates tried to prove $$2e \ge 3f$$ with numerical examples. Only a few candidates were able to prove this inequality correctly. In part (a) (ii), most candidates knew that $${K_5}$$ has 10 edges. However, a number of candidates simply drew a diagram with any number of faces and used this particular representation as a basis for their ‘proof’. Many candidates did not recognise the ‘hence’ requirement in part (a) (ii).

a.

In part (b) (i), many candidates stated the ‘handshaking lemma’ incorrectly by relating it to the ‘handshake problem’. In part (b) (ii), only a few candidates determined that $$v = e$$ and hence found that $$f = 2$$.

b.

In part (c), a reasonable number of candidates were able to draw a simple connected planar graph on $$6$$ vertices each of degree $$3$$. The most common error here was to produce a graph that contained a multiple edge(s).

c.

## Question

A simple connected planar graph, has $$e$$ edges, $$v$$ vertices and $$f$$ faces.

(i)     Show that $$2e \ge 3f{\text{ if }}v > 2$$.

(ii)     Hence show that $${K_5}$$, the complete graph on five vertices, is not planar.

[6]
a.

(i)     State the handshaking lemma.

(ii)     Determine the value of $$f$$, if each vertex has degree $$2$$.

[4]
b.

Draw an example of a simple connected planar graph on $$6$$ vertices each of degree $$3$$.

[2]
c.

## Markscheme

(i)     METHOD 1

attempting to use $$f = e – v + 2$$ and $$e \le 3v – 6$$ (if $$v > 2$$)     (M1)

$$2e \le 6v – 12 = 6(e – f + 2) – 12$$     M1A1

leading to $$2e \ge 3f$$     AG

METHOD 2

each face is bounded by at least three edges     A1

Note:     Award A1 for stating $$e \ge 3f$$.

each edge either separates two faces or, if an edge is interior to a face, it gets counted twice     R1

Note:     Award R1 for stating that each edge contributes two to the sum of the degrees of the faces (or equivalent) ie, $$\sum {\deg (F) = 2e}$$.

adding up the edges around each face     R1

leading to $$2e \ge 3f$$     AG

(ii)     $${K_5}$$ has $$e = 10$$     A1

if the graph is planar, $$f = 7$$     A1

this contradicts the inequality obtained above     R1

hence the graph is non-planar     AG

[6 marks]

a.

(i)     the sum of the vertex degrees $$= 2e$$ (or is even) or equivalent     A1

(ii)     if each vertex has degree $$2$$, then $$2v = 2e$$     A1

substituting $$v = e$$ into Euler’s formula     M1

$$f = 2$$     A1

[4 marks]

b.

for example,

A2

[2 marks]

Total [12 marks]

c.

## Examiners report

In part (a) (i), many candidates tried to prove $$2e \ge 3f$$ with numerical examples. Only a few candidates were able to prove this inequality correctly. In part (a) (ii), most candidates knew that $${K_5}$$ has 10 edges. However, a number of candidates simply drew a diagram with any number of faces and used this particular representation as a basis for their ‘proof’. Many candidates did not recognise the ‘hence’ requirement in part (a) (ii).

a.

In part (b) (i), many candidates stated the ‘handshaking lemma’ incorrectly by relating it to the ‘handshake problem’. In part (b) (ii), only a few candidates determined that $$v = e$$ and hence found that $$f = 2$$.

b.

In part (c), a reasonable number of candidates were able to draw a simple connected planar graph on $$6$$ vertices each of degree $$3$$. The most common error here was to produce a graph that contained a multiple edge(s).

c.

## Question

The following diagram shows the graph $$G$$.

Show that $$G$$ is bipartite.

[2]
a.

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

[1]
b.

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.

[2]
c.

$$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.

[3]
d.

Hence prove that for $$H$$

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

(ii)     $$e \le 2v – 4$$.

[3]
e.

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

[2]
f.

## Markscheme

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]

a.

$$C$$ and $$E$$     A1

[1 mark]

b.

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

(ii)     each edge bounds two faces     R1

[2 marks]

c.

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

d.

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

e.

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]

f.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

[N/A]

e.

[N/A]

f.

## Question

The following diagram shows the graph $$G$$.

Show that $$G$$ is bipartite.

[2]
a.

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

[1]
b.

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.

[2]
c.

$$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.

[3]
d.

Hence prove that for $$H$$

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

(ii)     $$e \le 2v – 4$$.

[3]
e.

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

[2]
f.

## Markscheme

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]

a.

$$C$$ and $$E$$     A1

[1 mark]

b.

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

(ii)     each edge bounds two faces     R1

[2 marks]

c.

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

d.

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

e.

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]

f.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

[N/A]

e.

[N/A]

f.

## Question

The simple, connected graph $$G$$ has e edges and $$v$$ vertices, where $$v \geqslant 3$$.

Given that both $$G$$ and $$G’$$ are planar and connected,

Show that the number of edges in $$G’$$, the complement of $$G$$, is $$\frac{1}{2}{v^2} – \frac{1}{2}v – e$$.

[2]
a.

show that the sum of the number of faces in $$G$$ and the number of faces in $$G’$$ is independent of $$e$$;

[3]
b.

show that $${v^2} – 13v + 24 \leqslant 0$$ and hence determine the maximum possible value of $$v$$.

[7]
c.

## Markscheme

the total number of edges in $$G$$ and $$G’$$ is $$\frac{{v(v – 1)}}{2}$$     (A1)

the number of edges in $$G’ = \frac{{v(v – 1)}}{2} – e$$     A1

$$= \frac{1}{2}{v^2} – \frac{1}{2}v – e$$    AG

[2 marks]

a.

using Euler’s formula, number of faces in $$G = e + 2 – v$$     A1

number of faces in $$G’ = \frac{{{v^2}}}{2} – \frac{v}{2} – e + 2 – v$$     A1

sum of these numbers $$= \frac{{{v^2}}}{2} – \frac{{5v}}{2} + 4$$     A1

this is independent of $$e$$     AG

[3 marks]

b.

for $$G$$ to be planar, we require     (M1)

$$e \leqslant 3v – 6$$    A1

for $$e \leqslant 3v – 6$$ to be planar, we require

$$\frac{{{v^2}}}{2} – \frac{v}{2} – e \leqslant 3v – 6$$    A1

for these two inequalities to be satisfied simultaneously, adding or substituting we require

$$\frac{{{v^2}}}{2} – \frac{v}{2} \leqslant 6v – 12$$    (M1)A1

leading to $${v^2} – 13v + 24 \leqslant 0$$     AG

the roots of the equation are 10.8 (and 2.23)     (A1)

the largest value of $$v$$ is therefore 10     A1

[7 marks]

c.

## Examiners report

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(a) If they considered the complete graph they were fine.

a.

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(b) Some confusion here if they were not clear about which graph they were applying Euler’s formula to. If they were methodical with good notation they obtained the answer.

b.

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(c) Again the same confusion about applying the inequality to both graphs. Most candidates realised which inequality was applicable. Many candidates had the good exam technique to pick up the last two marks even if they did not obtain the quadratic inequality.

c.

## Question

The simple, connected graph $$G$$ has e edges and $$v$$ vertices, where $$v \geqslant 3$$.

Given that both $$G$$ and $$G’$$ are planar and connected,

Show that the number of edges in $$G’$$, the complement of $$G$$, is $$\frac{1}{2}{v^2} – \frac{1}{2}v – e$$.

[2]
a.

show that the sum of the number of faces in $$G$$ and the number of faces in $$G’$$ is independent of $$e$$;

[3]
b.

show that $${v^2} – 13v + 24 \leqslant 0$$ and hence determine the maximum possible value of $$v$$.

[7]
c.

## Markscheme

the total number of edges in $$G$$ and $$G’$$ is $$\frac{{v(v – 1)}}{2}$$     (A1)

the number of edges in $$G’ = \frac{{v(v – 1)}}{2} – e$$     A1

$$= \frac{1}{2}{v^2} – \frac{1}{2}v – e$$    AG

[2 marks]

a.

using Euler’s formula, number of faces in $$G = e + 2 – v$$     A1

number of faces in $$G’ = \frac{{{v^2}}}{2} – \frac{v}{2} – e + 2 – v$$     A1

sum of these numbers $$= \frac{{{v^2}}}{2} – \frac{{5v}}{2} + 4$$     A1

this is independent of $$e$$     AG

[3 marks]

b.

for $$G$$ to be planar, we require     (M1)

$$e \leqslant 3v – 6$$    A1

for $$e \leqslant 3v – 6$$ to be planar, we require

$$\frac{{{v^2}}}{2} – \frac{v}{2} – e \leqslant 3v – 6$$    A1

for these two inequalities to be satisfied simultaneously, adding or substituting we require

$$\frac{{{v^2}}}{2} – \frac{v}{2} \leqslant 6v – 12$$    (M1)A1

leading to $${v^2} – 13v + 24 \leqslant 0$$     AG

the roots of the equation are 10.8 (and 2.23)     (A1)

the largest value of $$v$$ is therefore 10     A1

[7 marks]

c.

## Examiners report

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(a) If they considered the complete graph they were fine.

a.

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(b) Some confusion here if they were not clear about which graph they were applying Euler’s formula to. If they were methodical with good notation they obtained the answer.

b.

Generally in this question, good candidates thought their way through it whereas weak candidates just wrote down anything they could off the formula booklet or drew pictures of particular graphs. It was important to keep good notation and not let the same symbol stand for different things.

(c) Again the same confusion about applying the inequality to both graphs. Most candidates realised which inequality was applicable. Many candidates had the good exam technique to pick up the last two marks even if they did not obtain the quadratic inequality.

c.

## Question

Consider the complete bipartite graph $${\kappa _{3,\,3}}$$.

Draw $${\kappa _{3,\,3}}$$.

[1]
a.i.

Show that $${\kappa _{3,\,3}}$$ has a Hamiltonian cycle.

[1]
a.ii.

Draw $${\kappa _{3,\,2}}$$ and explain why it does not have a Hamiltonian cycle.

[2]
a.iii.

In the context of graph theory, state the handshaking lemma.

[1]
b.i.

Hence show that a graph G with degree sequence 2, 3, 3, 4, 4, 5 cannot exist.

[2]
b.ii.

Let T be a tree with $$v$$ where $$v$$ ≥ 2.

Use the handshaking lemma to prove that T has at least two vertices of degree one.

[4]
c.

## Markscheme

A1

[1 mark]

a.i.

for example ADBECFA       A1

Note: Accept drawing the cycle on their diagram.

Note: Accept Dirac’s theorem (although it is not on the syllabus for (a)(ii). There is no converse that could be applied for (a)(iii).

[1 mark]

a.ii.

A1

a Hamiltonian cycle would have to alternate between the two vertex subsets which is impossible as 2 ≠ 3      R1

Note: Award R1 for an attempt to construct a Hamiltonian cycle and an explanation of why it fails, eg, ADBEC but there is no route from C to A without re-using D or E so no cycle. There are other proofs eg, have to go in and out of A, similarly B and C giving all edges leading to a contradiction.

[2 marks]

a.iii.

the sum of the vertex degrees is twice the number of edges      A1

[1 mark]

b.i.

assume G exists

the sum 2 + 3 + 3 + 4 + 4 + 5 = 21      A1

this is odd (not even)      R1

this contradicts the handshaking lemma

so G does not exist      AG

[2 marks]

b.ii.

T has $$v – 1$$ edges     A1

EITHER

if $$k$$ vertices have degree 1 then $$v – k$$ vertices have degree ≥ 2     R1

by the handshaking lemma

$$2v – 2 \geqslant 1 \times k + 2\left( {v – k} \right)\left( { = 2v – k} \right)$$     M1

this gives $$k$$ ≥ 2    A1

OR

let S be the sum of vertex degrees

consider T having either no or one vertex of degree 1       R1

case 1 suppose T has no vertices of degree 1 (eg, all vertices have degrees ≥ 2)

by the handshaking lemma

$$S \geqslant 2v \ne 2\left( {v – 1} \right)$$ (not possible)      A1

case 2 suppose T has one vertex of degree 1 (eg, $$v – 1$$ vertices have degrees ≥ 2)

by the handshaking lemma

$$S \geqslant 2\left( {v – 1} \right) + 1 \ne 2\left( {v – 1} \right)$$ (not possible)      A1

THEN

so T has at least two vertices of degree 1     AG

[4 marks]

c.

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

a.iii.

[N/A]

b.i.

[N/A]

b.ii.

[N/A]

c.

## Question

Consider the complete bipartite graph $${\kappa _{3,\,3}}$$.

Draw $${\kappa _{3,\,3}}$$.

[1]
a.i.

Show that $${\kappa _{3,\,3}}$$ has a Hamiltonian cycle.

[1]
a.ii.

Draw $${\kappa _{3,\,2}}$$ and explain why it does not have a Hamiltonian cycle.

[2]
a.iii.

In the context of graph theory, state the handshaking lemma.

[1]
b.i.

Hence show that a graph G with degree sequence 2, 3, 3, 4, 4, 5 cannot exist.

[2]
b.ii.

Let T be a tree with $$v$$ where $$v$$ ≥ 2.

Use the handshaking lemma to prove that T has at least two vertices of degree one.

[4]
c.

## Markscheme

A1

[1 mark]

a.i.

for example ADBECFA       A1

Note: Accept drawing the cycle on their diagram.

Note: Accept Dirac’s theorem (although it is not on the syllabus for (a)(ii). There is no converse that could be applied for (a)(iii).

[1 mark]

a.ii.

A1

a Hamiltonian cycle would have to alternate between the two vertex subsets which is impossible as 2 ≠ 3      R1

Note: Award R1 for an attempt to construct a Hamiltonian cycle and an explanation of why it fails, eg, ADBEC but there is no route from C to A without re-using D or E so no cycle. There are other proofs eg, have to go in and out of A, similarly B and C giving all edges leading to a contradiction.

[2 marks]

a.iii.

the sum of the vertex degrees is twice the number of edges      A1

[1 mark]

b.i.

assume G exists

the sum 2 + 3 + 3 + 4 + 4 + 5 = 21      A1

this is odd (not even)      R1

this contradicts the handshaking lemma

so G does not exist      AG

[2 marks]

b.ii.

T has $$v – 1$$ edges     A1

EITHER

if $$k$$ vertices have degree 1 then $$v – k$$ vertices have degree ≥ 2     R1

by the handshaking lemma

$$2v – 2 \geqslant 1 \times k + 2\left( {v – k} \right)\left( { = 2v – k} \right)$$     M1

this gives $$k$$ ≥ 2    A1

OR

let S be the sum of vertex degrees

consider T having either no or one vertex of degree 1       R1

case 1 suppose T has no vertices of degree 1 (eg, all vertices have degrees ≥ 2)

by the handshaking lemma

$$S \geqslant 2v \ne 2\left( {v – 1} \right)$$ (not possible)      A1

case 2 suppose T has one vertex of degree 1 (eg, $$v – 1$$ vertices have degrees ≥ 2)

by the handshaking lemma

$$S \geqslant 2\left( {v – 1} \right) + 1 \ne 2\left( {v – 1} \right)$$ (not possible)      A1

THEN

so T has at least two vertices of degree 1     AG

[4 marks]

c.

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

a.iii.

[N/A]

b.i.

[N/A]

b.ii.

[N/A]

c.