# IB DP Maths Topic 10.7 Graphs, vertices, edges, faces. Adjacent vertices, adjacent edges. HL Paper 3

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

[6]
a.

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

[5]
b.

## Markscheme

The edges are included in the order

CF     A1

EF     A1

BC     A1

CD     A1

AB     A1

A1

[6 marks]

a.

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

b.

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

a.

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.

b.

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

[6]
a.

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.

[8]
b.

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

a.

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

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]

b.

## Examiners report

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

a.

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

b.

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

[5]
a.

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?

[12]
b.

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

a.

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

b.

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

a.

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

b.

## Question

The graph G has adjacency matrix M given below.

Draw the graph G .

[2]
a.

What information about G is contained in the diagonal elements of M$$^2$$ ?

[1]
b.

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

[3]
d.

## Markscheme

A2

Note: Award A1 if only one error, A0 for two or more.

[2 marks]

a.

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]

b.

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

Note: A1A1A1 for three correct with no additions; A1A1A0 for all correct, but with additions; A1A0A0 for two correct with or without additions.

[3 marks]

d.

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

a.

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.

b.

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.

d.

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

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.

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

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

[2]
a.

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

[4]
b.

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

[4]
c.

## Markscheme

complete graph on five vertices     A1

weights correctly marked on graph     A1

[2 marks]

a.

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]

b.

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]

c.
c.

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

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

[N/A]

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

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

[2]
a.

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

[3]
b.

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

[3]
c.

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

a.

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]

b.

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]

c.

[N/A]

a.

[N/A]

b.

[N/A]

c.

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

[1]
a.i.

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

[4]
a.ii.

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

[2]
b.

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

[4]
c.

## Markscheme

A1

[1 mark]

a.i.

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

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]

b.

$${\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]

c.

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

b.

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

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

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

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.

[2]
a.

Giving a reason, state whether or not G is

(i)     simple;

(ii)     connected;

(iii)     bipartite.

[4]
b.

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

[2]
c.

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

[1]
d.

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.

[4]
e.

## Markscheme

A2

[2 marks]

a.

(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 R1 is awarded.

[4 marks]

b.

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]

c.

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

[1 mark]

d.

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]

e.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

[N/A]

e.