## Question

The weighted graph *H *is shown below.

Use Kruskal’s Algorithm, indicating the order in which the edges are added, to find and draw the minimum spanning tree for *H*.

(i) A tree has *v *vertices. State the number of edges in the tree, justifying your answer.

(ii) We will call a graph with *v *vertices a “forest” if it consists of *c *components each of which is a tree.

Here is an example of a forest with 4 components.

How many edges will a forest with *v *vertices and *c *components have?

**Answer/Explanation**

## Markscheme

The edges are included in the order

CF *A1*

EF *A1*

BC *A1*

CD *A1*

AB *A1*

* A1*

*[6 marks]*

(i) A tree with *v *vertices has *v *−1 edges. *A1*

Using *v *+ *f *= *e *+ 2 with *f *= 1, the result follows. *R1*

(ii) Each of the *c *trees will have one less edge than the number of vertices. *R1*

Thus the forest will have *v *− *c *edges. *A2*

*[5 marks]*

## Examiners report

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result.

In (a), many candidates derived the minimum spanning tree although in some cases the method was not clearly indicated as required and some candidates used an incorrect algorithm. Part (b) was reasonably answered by many candidates although some justifications were unsatisfactory. Part (c) caused problems for many candidates who found difficulty in writing down a rigorous proof of the required result.

## Question

A graph has *n* vertices with degrees 1, 2, 3, …, *n*. Prove that \(n \equiv 0(\bmod 4)\) or \(n \equiv 3(\bmod 4)\).

Let *G* be a simple graph with *n* vertices, \(n \geqslant 2\). Prove, by contradiction, that at least two of the vertices of *G* must have the same degree.

**Answer/Explanation**

## Markscheme

as each edge contributes 1 to each of the vertices that it is incident with, each edge will contribute 2 to the sum of the degrees of all the vertices *(R1)*

so \(2e = \sum {{\text{degrees}}} \) *(A1)*

\(2e = \frac{{n(n + 1)}}{2}\) *A1*

\(4|n(n + 1)\) *A1*

*n* and *n* + 1 are coprime *R1*

**Note:** Accept equivalent reasoning *e.g.* only one of *n* and *n* + 1 can be even.

\(4|n{\text{ or }}4|n + 1\) *A1*

\(n \equiv 0(\bmod 4){\text{ or }}n \equiv 3(\bmod 4)\) *AG*

*[6 marks]*

since *G* is simple, the highest degree that a vertex can have is *n* – 1 *R1*

the degrees of the vertices must belong to the set \(S = \{ 0,{\text{ }}1,{\text{ }}2,{\text{ }} \ldots ,{\text{ }}n – 1\} \) *A1*

proof by contradiction

if no two vertices have the same degree, all *n* vertices must have different degrees *R1*

as there are only *n* different degrees in set *S*, the degrees must be precisely the *n* numbers 0, 1, 2, …, *n* – 1 *R1*

let the vertex with degree 0 be A, then A is not adjacent to any of the other vertices *R1*

let the vertex with degree *n* – 1 be B, then B is adjacent to all of the other vertices including A *R1R1*

this is our desired contradiction, so there must be two vertices of the same degree *R1*

*[8 marks]*

## Examiners report

Only the top candidates were able to produce logically, well thought-out proofs.

Only the top candidates were able to produce logically, well thought-out proofs.

## Question

A graph has *n* vertices with degrees 1, 2, 3, …, *n*. Prove that \(n \equiv 0(\bmod 4)\) or \(n \equiv 3(\bmod 4)\).

Let *G* be a simple graph with *n* vertices, \(n \geqslant 2\). Prove, by contradiction, that at least two of the vertices of *G* must have the same degree.

**Answer/Explanation**

## Markscheme

as each edge contributes 1 to each of the vertices that it is incident with, each edge will contribute 2 to the sum of the degrees of all the vertices *(R1)*

so \(2e = \sum {{\text{degrees}}} \) *(A1)*

\(2e = \frac{{n(n + 1)}}{2}\) *A1*

\(4|n(n + 1)\) *A1*

*n* and *n* + 1 are coprime *R1*

Note: Accept equivalent reasoning *e.g.* only one of *n* and *n* + 1 can be even.

\(4|n{\text{ or }}4|n + 1\) *A1*

\(n \equiv 0(\bmod 4){\text{ or }}n \equiv 3(\bmod 4)\) *AG*

*[6 marks]*

since *G* is simple, the highest degree that a vertex can have is *n* – 1 *R1*

the degrees of the vertices must belong to the set \(S = \{ 0,{\text{ }}1,{\text{ }}2,{\text{ }} \ldots ,{\text{ }}n – 1\} \) *A1*

proof by contradiction

if no two vertices have the same degree, all *n* vertices must have different degrees *R1*

as there are only *n* different degrees in set *S*, the degrees must be precisely the *n* numbers 0, 1, 2, …, *n* – 1 *R1*

let the vertex with degree 0 be A, then A is not adjacent to any of the other vertices *R1*

let the vertex with degree *n* – 1 be B, then B is adjacent to all of the other vertices including A *R1R1*

this is our desired contradiction, so there must be two vertices of the same degree *R1*

*[8 marks]*

## Examiners report

Only the top candidates were able to produce logically, well thought-out proofs.

Only the top candidates were able to produce logically, well thought-out proofs.

## Question

In any graph, show that

(i) the sum of the degrees of all the vertices is even;

(ii) there is an even number of vertices of odd degree.

Consider the following graph, *M*.

(i) Show that *M* is planar.

(ii) Explain why *M* is not Eulerian.

(iii) By adding one edge to *M* it is possible to make it Eulerian. State which edge must be added.

This new graph is called *N*.

(iv) Starting at A, write down a possible Eulerian circuit for *N*.

(v) Define a Hamiltonian cycle. If possible, write down a Hamiltonian cycle for *N*, and if not possible, give a reason.

(vi) Write down the adjacency matrix for *N*.

(vii) Which pair of distinct vertices has exactly 30 walks of length 4 between them?

**Answer/Explanation**

## Markscheme

(i) When we sum over the degrees of all vertices, we count each edge twice. Hence every edge adds two to the sum. Hence the sum of the degrees of all the vertices is even. *R2*

* *

(ii) divide the vertices into two sets, those with even degree and those with odd degree *M1*

let *S* be the sum of the degrees of the first set and let *T* be the sum of the degrees of the second set

we know *S* + *T* must be even

since *S* is the sum of even numbers, then it is even *R1*

hence *T* must be even *R1*

hence there must be an even number of vertices of odd degree *AG*

*[5 marks]*

(i)

*A1*

(ii) the graph *M* is not Eulerian because vertices D and F are of odd degree *A1*

(iii) the edge which must be added is DF *A1*

(iv)

a possible Eulerian circuit is ABDFBCDEFGCA *A2*

**Note:** award ** A1** for a correct Eulerian circuit not starting and finishing at A.

(v) a Hamiltonian cycle is one that contains each vertex in *N* *A1*

with the exception of the starting and ending vertices, each vertex must only appear once *A1*

a possible Hamiltonian cycle is ACGFEDBA *A1*

(vi) \(\left( {\begin{array}{*{20}{c}}

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

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

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

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

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

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

0&0&1&0&0&1&0

\end{array}} \right)\) *A2*

(vii) using adjacency matrix to power 4 *(M1)*

C and F *A1** *

*[12 marks]*

## Examiners report

Most candidates were able to start (a), but many found problems in expressing their ideas clearly in words. Stronger candidates had little problem with (b), but a significant number of weaker candidates had problems working with the concepts of Eulerian circuits and Hamiltonian cycles and with understanding how to find a specific number of walks of a certain length as required in (b) (vii).

Most candidates were able to start (a), but many found problems in expressing their ideas clearly in words. Stronger candidates had little problem with (b), but a significant number of weaker candidates had problems working with the concepts of Eulerian circuits and Hamiltonian cycles and with understanding how to find a specific number of walks of a certain length as required in (b) (vii).

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

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

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]