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

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

The following figure shows the floor plan of a museum.

(a) (i) Draw a graph *G *that represents the plan of the museum where each exhibition room is represented by a vertex labelled with the exhibition room number and each door between exhibition rooms is represented by an edge. Do not consider the entrance foyer as a museum exhibition room.

(ii) Write down the degrees of the vertices that represent each exhibition room.

(iii) Virginia enters the museum through the entrance foyer. Use your answers to (i) and (ii) to justify why it is possible for her to visit the thirteen exhibition rooms going through each internal doorway exactly once.

(b) Let *G *and *H *be two graphs whose adjacency matrices are represented below.

Using the adjacency matrices,

(i) find the number of edges of each graph;

(ii) show that exactly one of the graphs has a Eulerian trail;

(iii) show that neither of the graphs has a Eulerian circuit.

**Answer/Explanation**

## Markscheme

(a) (i)

*(M1)A1*

**Note: **Do not penalize candidates who include the entrance foyer.

(ii) the degrees of the vertices are 4, 2, 4, 4, 2, 2, 4, 2, 2, 2, 2, 2, 2 *A1*

(iii) the degree of all vertices is even and hence a Eulerian circuit exists, *A1*

hence it is possible to enter the museum through the foyer and visit each room 1–13 going through each internal doorway exactly once *AG*

**Note: **The connected graph condition is not required.

*[4 marks]*

(b) (i)

*(M1)*

graph *G *has 15 edges and graph *H *has 22 edges *A1A1*

(ii) the degree of every vertex is equal to the sum of the numbers in the corresponding row (or column) of the adjacency table

exactly two of the vertices of *G *have an odd degree (B and C) *A1*

*H *has four vertices with odd degree *A1*

*G *is the graph that has a Eulerian trail (and *H *does not) *R1*

(iii) neither graph has all vertices of even degree *R1*

therefore neither of them has a Eulerian circuit *AG*

*[7 marks]*

## Examiners report

Part (a) was generally well answered. There were many examples of full marks in this part. Part (b) caused a few more difficulties, although there were many good solutions. Few candidates used the matrix to find the number of edges, preferring instead to draw the graph. A surprising number of students confused the ideas of having vertices of odd degree.

## Question

The weighted graph *K*, representing the travelling costs between five customers, has the following adjacency table.

Draw the graph \(K\).

Starting from customer D, use the nearest-neighbour algorithm, to determine an upper bound to the travelling salesman problem for *K*.

By removing customer A, use the method of vertex deletion, to determine a lower bound to the travelling salesman problem for *K*.

**Answer/Explanation**

## Markscheme

complete graph on five vertices *A1*

weights correctly marked on graph *A1*

*[2 marks]*

clear indication that the nearest-neighbour algorithm has been applied *M1*

DA (or 7) *A1*

AB (or 1) BC (or 9) *A1*

CE (or 3), ED (or 12), giving UB = 32 *A1*

*[4 marks]*

attempt to use the vertex deletion method *M1*

minimum spanning tree is ECBD *A1*

(EC 3, BD 8, BC 9 total 20)

reconnect A with the two edges of least weight, namely AB (1) and AE (4) *M1*

lower bound is 25 *A1*

*[4 marks]*

## Question

(a) Draw a spanning tree for

(i) the complete graph, \({K_4}\);

(ii) the complete bipartite graph, \({K_{4,4}}\).

(b) Prove that a simple connected graph with *n *vertices, where \(n > 1\), must have two vertices

of the same degree.

(c) Prove that every simple connected graph has at least one spanning tree.

**Answer/Explanation**

## Markscheme

**Note: **Other trees are possible, but must clearly come from the bipartite graph, so, for example, a straight line graph is not acceptable unless the bipartite nature is clearly shown *eg*, with black and white vertices.

*[2 marks]*

* *

(b) graph is simple implies maximum degree is \(n – 1\) *A1*

graph is connected implies minimum degree is 1 *A1*

by a pigeon-hole principle two vertices must have the same degree *R1*

*[3 marks]*

* *

(c) if the graph is not a tree it contains a cycle *A1*

remove one edge of this cycle *M1*

the graph remains connected *A1*

repeat until there are no cycles *M1*

the final graph is connected and has no cycles *A1*

so is a tree *AG*

**Note: **Allow other methods *eg*, induction, reference to Kruskal’s algorithm.

*[5 marks]*

* *

*Total [10 marks]*

## Examiners report

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

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

show that the sum of the number of faces in \(G\) and the number of faces in \(G’\) is independent of \(e\);

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

**Answer/Explanation**

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

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

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

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

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.

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.

## Question

In this question no graphs are required to be drawn. Use the handshaking lemma and other results about graphs to explain why,

a graph cannot exist with a degree sequence of \(1,{\text{ }}2,{\text{ }}3,{\text{ }}4,{\text{ }}5,{\text{ }}6,{\text{ }}7,{\text{ }}8,{\text{ }}9\);

a simple, connected, planar graph cannot exist with a degree sequence of \(4,{\text{ }}4,{\text{ }}4,{\text{ }}4,{\text{ }}5,{\text{ }}5\);

a tree cannot exist with a degree sequence of \(1,{\text{ }}1,{\text{ }}2,{\text{ }}2,{\text{ }}3,{\text{ }}3\).

**Answer/Explanation**

## Markscheme

assume such a graph exists

by the handshaking lemma the sum of the degrees equals twice the number of edges *R1*

but \(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45\) which is odd *R1*

this is a contradiction so graph does not exist *AG*

*[2 marks]*

assume such a graph exists

since the graph is simple and connected (and \(v = 6 > 2\)) then \(e \leqslant 3v – 6\) *R1*

by the handshaking lemma \(4 + 4 + 4 + 4 + 5 + 5 = 2e\) so \(e = 13\) *A1*

hence \(13 \leqslant 3 \times 6 – 6 = 12\) *A1*

this is a contradiction so graph does not exist *AG*

*[3 marks]*

assume such a graph exists

a tree with 6 vertices must have 5 edges (since \({\text{V}} – {\text{E}} + 1 = 2\) for a tree) *R1*

using the Handshaking Lemma \(1 + 1 + 2 + 2 + 3 + 3 = 2 \times 5\) implies \(12 = 10\) *M1A1*

this is a contradiction so graph does not exist *AG*

*[3 marks]*

## Examiners report

[N/A]

[N/A]

[N/A]

## Question

Consider \({\kappa _n}\), a complete graph with \(n\) vertices, \(n \geqslant 2\). Let \(T\) be a fixed spanning tree of \({\kappa _n}\).

Draw the complete bipartite graph \({\kappa _{3,3}}\).

Prove that \({\kappa _{3,3}}\) is not planar.

A connected graph \(G\) has \(v\) vertices. Prove, using Euler’s relation, that a spanning tree for \(G\) has \(v – 1\) edges.

If an edge \(E\) is chosen at random from the edges of \({\kappa _n}\), show that the probability that \(E\) belongs to \(T\) is equal to \(\frac{2}{n}\).

**Answer/Explanation**

## Markscheme

*A1*

*[1 mark]*

assume \({\kappa _{3,3}}\) is planar

\({\kappa _{3,3}}\) has no cycles of length 3 *R1*

use of \(e \leqslant 2v – 4\) *M1*

\(e = 9\) and \(v = 6\) *A1*

hence inequality not satisfied 9 \(\not \leqslant \) 8 *R1*

so \({\kappa _{3,3}}\) is not planar *AG*

**Note:** use of \(e \leqslant 3v – 6\) with \(e = 9\) and \(v = 6\) and concluding that this inequality does not show whether \({\kappa _{3,3}}\) is planar or not just gains ** R1**.

*[4 marks]*

a spanning tree (is planar and) has one face *A1*

Euler’s relation is \(v – e + f = 2\)

\(v – e + 1 = 2\) *M1*

\( \Rightarrow e = v – 1\) *AG*

*[2 marks]*

\({\kappa _n}\) has \(\left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right)\) edges \(\left( {\frac{{n(n – 1)}}{2}{\text{ edges}}} \right)\) *(A1)*

\({\text{P}}(E{\text{ belongs to }}T) = \frac{{n – 1}}{{\left( {\frac{{n(n – 1)}}{2}} \right)}}\) *M1A1*

clear evidence of simplification of the above expression *M1*

\( = \frac{2}{n}\) *AG*

*[4 marks]*

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

## Question

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

Draw \({\kappa _{3,\,3}}\).

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

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

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

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

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.

**Answer/Explanation**

## Markscheme

*A1*

*[1 mark]*

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

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

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

*[1 mark]*

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

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

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]

## Question

The graph *G* has vertices *P* , *Q* , *R* , *S* , *T* and the following table shows the number of edges joining each pair of vertices.

Draw the graph *G* as a planar graph.

Giving a reason, state whether or not *G* is

(i) simple;

(ii) connected;

(iii) bipartite.

Explain what feature of *G* enables you to state that it has an Eulerian trail and write down a trail.

Explain what feature of *G* enables you to state it does not have an Eulerian circuit.

Find the maximum number of edges that can be added to the graph *G* (not including any loops or further multiple edges) whilst still keeping it planar.

**Answer/Explanation**

## Markscheme

* A2*

*[2 marks]*

(i) *G* is not simple because 2 edges join P to T *R1*

* *

(ii) *G* is connected because there is a path joining every pair of vertices *R1*

* *

(iii) (P, R) and (Q, S, T) are disjoint vertices *R1*

so *G* is bipartite *A1*

**Note:** Award the ** A1** only if the

**is awarded.**

*R1** *

*[4 marks]*

*G* has an Eulerian trail because it has two vertices of odd degree (R and T have degree 3), all the other vertices having even degree *R1*

the following example is such a trail

TPTRSPQR *A1*

*[2 marks]*

*G* has no Eulerian circuit because there are 2 vertices which have odd degree *R1*

*[1 mark]*

consider

so it is possible to add 3 extra edges *A1*

consider *G* with one of the edges PT deleted; this is a simple graph with 6 edges; on addition of the new edges, it will still be simple *M1*

\(e \leqslant 3v – 6 \Rightarrow e \leqslant 3 \times 5 – 6 = 9\) *R1*

so at most 3 edges can be added *R1*

*[4 marks]*

## Examiners report

[N/A]

[N/A]

[N/A]

[N/A]

[N/A]