## Question

The graph *G *has the following cost adjacency table.

\[\begin{array}{*{20}{c|ccccc}}

{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\

\hline

{\text{A}}& {\text{ – }}&9&{\text{ – }}&8&4 \\

{\text{B}}& 9&{\text{ – }}&7&{\text{ – }}&2 \\

{\text{C}}& {\text{ – }}&7&{\text{ – }}&7&3 \\

{\text{D}}& 8&{\text{ – }}&7&{\text{ – }}&5 \\

{\text{E}}& 4&2&3&5&{\text{ – }}

\end{array}\]

Draw *G *in a planar form.

Giving a reason, determine the maximum number of edges that could be added to *G *while keeping the graph both simple and planar.

List all the distinct Hamiltonian cycles in *G *beginning and ending at A, noting that two cycles each of which is the reverse of the other are to be regarded as identical. Hence determine the Hamiltonian cycle of least weight.

**Answer/Explanation**

## Markscheme

*A2*

*[2 marks]*

For a simple planar graph containing triangles, \(e \leqslant 3v – 6\) *M1*

Here \(v = 5{\text{ , so }}e \leqslant 9\) . *A1*

There are already 8 edges so the maximum number of edges that could be added is 1. *R1*

This can be done *e.g. *AC or BD *R1*

*[4 marks]*

The distinct Hamiltonian cycles are

ABCDEA *A2*

ABCEDA *A2*

ABECDA *A2*

AEBCDA *A2*

**Note: **Do not penalise extra cycles.

The weights are 32, 32, 29, 28 respectively. *A1*

The Hamiltonian cycle of least weight is AEBCDA. *R1*

*[10 marks]*

## Examiners report

A fairly common error in (a) was to draw a non-planar version of *G*, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

A fairly common error in (a) was to draw a non-planar version of *G*, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

A fairly common error in (a) was to draw a non-planar version of *G*, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.

## Question

Prove that a graph containing a triangle cannot be bipartite.

Prove that the number of edges in a bipartite graph with *n *vertices is less than or equal to \(\frac{{{n^2}}}{4}\).

**Answer/Explanation**

## Markscheme

At least two of the three vertices in the triangle must lie on one of the two disjoint sets *M1R1*

These two are joined by an edge so the graph cannot be bipartite *R1*

*[3 marks]*

If there are *x* vertices in one of the two disjoint sets then there are (*n* – *x*) vertices in the other disjoint set **M1**

The greatest number of edges occurs when all vertices in one set are joined to all vertices in the other to give *x*(*n* – *x*) edges **A1**

Function *f*(*x*) = *x*(*n – x*) has a parabolic graph. *M1*

This graph has a unique maximum at \(\left( {\frac{n}{2},\frac{{{n^2}}}{4}} \right)\). *A1*

so \(x(n – x) \leqslant \frac{{{n^2}}}{4}\) *R1*

*[5 marks]*

## Examiners report

Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.

Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.

## Question

(a) A connected planar graph *G *has *e *edges and *v *vertices.

(i) Prove that \(e \geqslant v – 1\).

(ii) Prove that *e *= *v *−1 if and only if *G *is a tree.

(b) A tree has *k *vertices of degree 1, two of degree 2, one of degree 3 and one of degree 4. Determine *k *and hence draw a tree that satisfies these conditions.

(c) The graph *H *has the adjacency table given below.

\[\left( {\begin{array}{*{20}{c}}

0&1&1&0&0&0 \\

1&0&0&1&1&0 \\

1&0&0&0&1&1 \\

0&1&0&0&0&0 \\

0&1&1&0&0&0 \\

0&0&1&0&0&0

\end{array}} \right)\]

(i) Explain why *H *cannot be a tree.

(ii) Draw the graph of *H *.

(d) Prove that a tree is a bipartite graph.

**Answer/Explanation**

## Markscheme

(a) (i) Euler’s relation is

\(e = v – 2 + f \geqslant v – 1,{\text{ as }}f \geqslant 1\) *M1A1*

* *

(ii) \(G{\text{ is a tree }} \Leftrightarrow {\text{ no cycles }} \Leftrightarrow {\text{ }}f = 1\) *R1R1*

*[4 marks]*

* *

(b) the result from (a) (ii) gives

\(e = k + 2 + 1 + 1 – 1 = k + 3\) *M1A1*

for a tree we also have

\(2e = {\text{sum of degrees}}\) *M1*

\(2k + 6 = k + 4 + 3 + 4 = k + 11\)

hence \(k = 5\) *A1*

*A2*

**Note:** Accept alternative correct solutions.

*[6 marks]*

(c) (i) \(v – 1 = 5 < 6 = e\,\,\,\,\,{\text{by (a) (ii)}}\) *M1A1*

*G* cannot be a tree *AG*

(ii) *A1*

*[3 marks]*

(d) take any vertex in the tree and colour it black *M1*

colour all adjacent vertices white

colour all vertices adjacent to a white vertex black

continue this procedure until all vertices are coloured *M1*

which must happen since the graph is connected *R1*

as the tree contains no cycles, no vertex can be both black and white and the graph is proved to be bipartite *R1*

*[4 marks]*

*Total [17 marks]*

## Examiners report

Many candidates seem only to have a weak understanding of the requirements for the proof of a mathematical statement.

## Question

The planar graph *G* and its complement \(G’\) are both simple and connected.

Given that *G* has 6 vertices and 10 edges, show that \(G’\) is a tree.

**Answer/Explanation**

## Markscheme

the complete graph with 6 vertices has 15 edges so \(G’\) has

6 vertices and 5 edges *M1A1*

the number of faces in \(G’\) , \(f = 2 + e – v = 1\) *M1A1*

it is therefore a tree because \(f = 1\) **R1**

**Note:** Accept it is a tree because \(v = e + 1\)

*[5 marks]*

## Examiners report

Part (a) was well answered by many candidates.

## Question

Show that a graph is bipartite if and only if it contains only cycles of even length.

**Answer/Explanation**

## Markscheme

Suppose the graph is bipartite so that the vertices belong to one of two disjoint sets M, N. *M1*

Then consider any vertex V in M. To generate a cycle returning to V, we must go to a vertex in N, then to a vertex in M, then to a vertex in N, then to a vertex in M, *etc.* *R1*

To return to V, therefore, which belongs to M, an even number of steps will be required. *R1*

Now suppose the graph contains only cycles of even length. *M1*

Starting at any vertex V, define the set M as containing those vertices accessible from V in an even number of steps and the set N as containing those vertices accessible from V in an odd number of steps. *R1*

Suppose that the vertex X belongs to both M and N. Then consider the closed walk from V to X one way and back to V the other way. This closed walk will be of odd length. This closed walk can be contracted to a cycle which will also be of odd length, giving a contradiction to the initial assumption. *R1*

There can therefore be no vertices common to M and N which shows that the vertices can be divided into two disjoint sets and the graph is bipartite. *R1*

Consider any edge joining P to vertex Q. Then either \({\text{P}} \in {\text{M}}\) in which case \({\text{Q}} \in {\text{M}}\) or vice versa. In either case an edge always joins a vertex in M to a vertex in N so the graph is bipartite. *R1*

*[8 marks]*

## Examiners report

Many candidates made a reasonable attempt at showing that bipartite implies cycles of even length but few candidates even attempted the converse.

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

**Answer/Explanation**

## 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* + *f* – *e* 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* + *f* – *e* 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

The vertices of a graph *L* are A, B, C, D, E, F, G and H. The weights of the edges in *L* are given in the following table.

Draw the graph *L*.

**Answer/Explanation**

## Markscheme

*A2*

**Note:** Award ** A1** if one line missing or one line misplaced. Weights are not required.

*[2 marks]*

## Examiners report

Most candidates were able to draw the graph as required in (a) and most made a meaningful start to applying Prim’s algorithm in (b). Candidates were not always clear about the order in which the edges were to be added.

## Question

The graph *G *has adjacency matrix ** M **given below.

Draw the graph *G *.

What information about *G *is contained in the diagonal elements of * M*\(^2\) ?

List the trails of length 4 starting at A and ending at C.

**Answer/Explanation**

## Markscheme

* A2*

* *

**Note: **Award ** A1 **if only one error,

**for two or more.**

*A0**[2 marks]*

the (*k*, *k*) element of * M*\(^2\) is the number of vertices directly connected to vertex

*k*

*A1*

**Note: **Accept comment about the number of walks of length 2, in which the initial and final vertices coincide.

*[1 mark]*

the trails of length 4 are ABEDC, AFEDC, AFEBC *A1A1A1*** **

**Note: A1A1A1 **for three correct with no additions;

**for all correct, but with additions;**

*A1A1A0***for two correct with or without additions.**

*A1A0A0**[3 marks]*

## Examiners report

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

Parts (a) and (c) were generally correctly answered. In part (b), a minority of candidates failed to mention that the starting and end points had to coincide. A large number of candidates gave all walks (trails were asked for) – an unnecessary loss of marks.

## Question

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

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 4*n *or 4*n *+ 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.

**Answer/Explanation**

## Markscheme

as a first step, form the following graph

*(M1)(A1)*

make it planar

* A1*

*[3 marks]*

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

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

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.

## Question

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

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 4*n *or 4*n *+ 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.

**Answer/Explanation**

## Markscheme

as a first step, form the following graph

*(M1)(A1)*

make it planar

* A1*

*[3 marks]*

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

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

## Question

Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.

Seventeen people attend a meeting.

Each person shakes hands with at least one other person and no-one shakes hands with

the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.

Explain why each person cannot have shaken hands with exactly nine other people.

**Answer/Explanation**

## Markscheme

let there be *\(v\) *vertices in the graph; because the graph is simple the degree of each vertex is \( \le v – 1\) *A1*

the degree of each vertex is \( \ge 1\) *A1*

there are therefore \(v – 1\) possible values for the degree of each vertex *A1*

given there are *\(v\) *vertices by the pigeon-hole principle there must be at least two with the same degree *R1*

*[4 marks]*

consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands *M1*

the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves) *A1*

every vertex is connected to at least one other vertex as everyone shakes at least one hand *A1*

the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands *R1*

**Note: **Accept answers starting afresh rather than quoting part (a).

**[4 marks]**

(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number *A1*

the degree of each vertex would be *\(9\)* and \(9 \times 17\) is an odd number (giving a contradiction) *A1*

*[2 marks]*

*Total [10 marks]*

## Examiners report

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Misconceptions were: thinking that a few examples constituted a proof, thinking that the graph had to be connected, taking the edges as the pigeons not the degrees. The pigeon-hole principle was known but not always applied well.

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Similar problems as in (a).

Generally there were too many “waffly” words and not enough precise statements leading to conclusions.

Many spurious reasons were given but good candidates went straight to the hand-shaking lemma.

## Question

Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.

Seventeen people attend a meeting.

Each person shakes hands with at least one other person and no-one shakes hands with

the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.

Explain why each person cannot have shaken hands with exactly nine other people.

**Answer/Explanation**

## Markscheme

let there be *\(v\) *vertices in the graph; because the graph is simple the degree of each vertex is \( \le v – 1\) *A1*

the degree of each vertex is \( \ge 1\) *A1*

there are therefore \(v – 1\) possible values for the degree of each vertex *A1*

given there are *\(v\) *vertices by the pigeon-hole principle there must be at least two with the same degree *R1*

*[4 marks]*

consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands *M1*

the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves) *A1*

every vertex is connected to at least one other vertex as everyone shakes at least one hand *A1*

the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands *R1*

**Note: **Accept answers starting afresh rather than quoting part (a).

**[4 marks]**

(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number *A1*

the degree of each vertex would be *\(9\)* and \(9 \times 17\) is an odd number (giving a contradiction) *A1*

*[2 marks]*

*Total [10 marks]*

## Examiners report

Misconceptions were: thinking that a few examples constituted a proof, thinking that the graph had to be connected, taking the edges as the pigeons not the degrees. The pigeon-hole principle was known but not always applied well.

Similar problems as in (a).

Many spurious reasons were given but good candidates went straight to the hand-shaking lemma.

## Question

The weights of the edges of a graph \(H\) are given in the following table.

(i) Draw the weighted graph \(H\).

(ii) Use Kruskal’s algorithm to find the minimum spanning tree of \(H\). Your solution should indicate the order in which the edges are added.

(iii) State the weight of the minimum spanning tree.

Consider the following weighted graph.

(i) Write down a solution to the Chinese postman problem for this graph.

(ii) Calculate the total weight of the solution.

(i) State the travelling salesman problem.

(ii) Explain why there is no solution to the travelling salesman problem for this graph.

**Answer/Explanation**

## Markscheme

(i) *A2*

**Note: **Award ** A1 **if one edge is missing. Award

**if the edge weights are not labelled.**

*A1*(ii) the edges are added in the order:

\(FG{\rm{ }}1\) *M1A1*

\(CE{\rm{ }}2\) *A1*

\(ED{\rm{ }}3\)

\(EG{\rm{ }}4\) *A1*

\(AC{\rm{ }}4\)

**Note: **\(EG\) and \(AC\) can be added in either order.

(Reject \(EF\))

(Reject \(CD\))

\(EB5\) **OR **\(AB5\) *A1*

**Notes: **The minimum spanning tree does not have to be seen.

If only a tree is seen, the order by which edges are added must be clearly indicated.

(iii) \(19\) *A1*

*[8 marks]*

(i) *eg*, \(PQRSRTSTQP\) **OR **\(PQTSTRSRQP\) *M1A1*

**Note: **Award ** M1 **if in either (i) or (ii), it is recognised that edge \(PQ\) is needed twice.

(ii) total weight \( = 34\) *A1*

*[3 marks]*

(i) to determine a cycle where each vertex is visited once only (Hamiltonian cycle) *A1*

of least total weight *A1*

(ii) **EITHER**

to reach \(P\), \(Q\) must be visited twice which contradicts the definition of the \(TSP\) *R1*

**OR**

the graph is not a complete graph and hence there is no solution to the \(TSP\) *R1 *

*[3 marks]*

*Total [14 marks]*

## Examiners report

Part (a) was generally very well answered. Most candidates were able to correctly sketch the graph of \(H\) and apply Kruskal’s algorithm to determine the minimum spanning tree of \(H\). A few candidates used Prim’s algorithm (which is no longer part of the syllabus).

Most candidates understood the Chinese Postman Problem in part (b) and knew to add the weight of \(PQ\) to the total weight of \(H\). Some candidates, however, did not specify a solution to the Chinese Postman Problem while other candidates missed the fact that a return to the initial vertex is required.

In part (c), many candidates had trouble succinctly stating the Travelling Salesman Problem. Many candidates used an ‘edge’ argument rather than simply stating that the Travelling Salesman Problem could not be solved because to reach vertex \(P\), vertex \(Q\) had to be visited twice.

## Question

The graph \({K_{2,{\text{ }}2}}\) is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.

Draw \({K_{2,{\text{ }}2}}\) as a planar graph.

Draw a spanning tree for \({K_{2,{\text{ }}2}}\).

Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).

Show that the complement of any complete bipartite graph does not possess a spanning tree.

**Answer/Explanation**

## Markscheme

* A1A1*

**Note: **Award ** A1 **for a correct version of \({K_{2,{\text{ }}2}}\) and

**for a correct planar representation.**

*A1***[2 marks]**

* **A1*

*[1 mark]*

* A1*

*[1 mark]*

the complete bipartite graph \({K_{m,{\text{ }}n}}\) has two subsets of vertices \(A\) and \(B\), such that each element of \(A\) is connected to every element of \(B\) *A1*

in the complement, no element of \(A\) is connected to any element of \(B\). The complement is not a connected graph *A1*

by definition a tree is connected *R1*

hence the complement of any complete bipartite graph does not possess a spanning tree *AG*

*[3 marks]*

*Total [7 marks]*

## Examiners report

Part (a) was generally well done with a large number of candidates drawing a correct planar representation for \({K_{2,2}}\). Some candidates, however, produced a correct non-planar representation of \({K_{2,2}}\).

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).

Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of \({K_{m,n}}\) does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.

## Question

The graph \({K_{2,{\text{ }}2}}\) is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.

Draw \({K_{2,{\text{ }}2}}\) as a planar graph.

Draw a spanning tree for \({K_{2,{\text{ }}2}}\).

Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).

Show that the complement of any complete bipartite graph does not possess a spanning tree.

**Answer/Explanation**

## Markscheme

* A1A1*

**Note: **Award ** A1 **for a correct version of \({K_{2,{\text{ }}2}}\) and

**for a correct planar representation.**

*A1***[2 marks]**

* **A1*

*[1 mark]*

*A1**[1 mark]*

the complete bipartite graph \({K_{m,{\text{ }}n}}\) has two subsets of vertices \(A\) and \(B\), such that each element of \(A\) is connected to every element of \(B\) *A1*

in the complement, no element of \(A\) is connected to any element of \(B\). The complement is not a connected graph *A1*

by definition a tree is connected *R1*

hence the complement of any complete bipartite graph does not possess a spanning tree *AG*

*[3 marks]*

*Total [7 marks]*

## Examiners report

Part (a) was generally well done with a large number of candidates drawing a correct planar representation for \({K_{2,2}}\). Some candidates, however, produced a correct non-planar representation of \({K_{2,2}}\).

Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).

Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of \({K_{m,n}}\) does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.

## Question

The graph \({K_{2,{\text{ }}2}}\) is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.

Draw \({K_{2,{\text{ }}2}}\) as a planar graph.

Draw a spanning tree for \({K_{2,{\text{ }}2}}\).

Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).

Show that the complement of any complete bipartite graph does not possess a spanning tree.

**Answer/Explanation**

## Markscheme

* A1A1*

**Note: **Award ** A1 **for a correct version of \({K_{2,{\text{ }}2}}\) and

**for a correct planar representation.**

*A1***[2 marks]**

* **A1*

*[1 mark]*

* A1*

*[1 mark]*

the complete bipartite graph \({K_{m,{\text{ }}n}}\) has two subsets of vertices \(A\) and \(B\), such that each element of \(A\) is connected to every element of \(B\) *A1*

in the complement, no element of \(A\) is connected to any element of \(B\). The complement is not a connected graph *A1*

by definition a tree is connected *R1*

hence the complement of any complete bipartite graph does not possess a spanning tree *AG*

*[3 marks]*

*Total [7 marks]*

## Examiners report

Part (a) was generally well done with a large number of candidates drawing a correct planar representation for \({K_{2,2}}\). Some candidates, however, produced a correct non-planar representation of \({K_{2,2}}\).

Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of \({K_{m,n}}\) does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.

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

(i) State the handshaking lemma.

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

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

**Answer/Explanation**

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

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

for example,

**A2**

**[2 marks]**

**Total [12 marks]**

## 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).

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\).

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

## Question

The following diagram shows the graph \(G\).

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.

**Answer/Explanation**

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

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

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]