IB DP Maths Topic 10.7 Simple graphs; connected graphs; complete graphs; HL Paper 3

 

https://play.google.com/store/apps/details?id=com.iitianDownload IITian Academy  App for accessing Online Mock Tests and More..

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.

[2]
a.

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

[4]
b.

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.

[10]
c.
Answer/Explanation

Markscheme

     A2

[2 marks]

a.

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]

b.

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]

c.

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.

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.

b.

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.

c.

Question

Prove that a graph containing a triangle cannot be bipartite.

[3]
b.

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

[5]
c.
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]

b.

If there are x vertices in one of the two disjoint sets then there are (nx) 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(nx) 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]

c.

Examiners report

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

b.

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

c.

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 + fe remains equal to 2     M1A1

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

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

[7 marks]

 

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

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

hence \(3f \leqslant 2e\)     AG

from the Euler relation, \(3f = 6 + 3e – 3v\)     M1

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

hence \(e \leqslant 3v – 6\)     AG

[4 marks]

 

(c)     let G have e edges     M1

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

it follows that \({G’}\) has 66 – e edges     A1

for planarity we require

\(e \leqslant 3 \times 12 – 6 = 30\)     M1A1

and \(66 – e \leqslant 30 \Rightarrow e \geqslant 36\)     A1

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

[7 marks]

Total [18 marks]

Examiners report

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

Question

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 .

[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.
Answer/Explanation

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.
Answer/Explanation

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

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.
Answer/Explanation

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

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.

[4]
a.

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.

[4]
b.

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

[2]
c.
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]

a.

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]

b.

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

c.

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.

a.

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

Similar problems as in (a).

b.

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.

c.

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.

[4]
a.

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.

[4]
b.

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

[2]
c.
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]

a.

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]

b.

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

c.

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.

a.

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

Similar problems as in (a).

b.

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.

c.

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.

[8]
a.

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.

[3]
b.

(i)     State the travelling salesman problem.

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

[3]
c.
Answer/Explanation

Markscheme

(i)          A2

Note:     Award A1 if one edge is missing. Award A1 if the edge weights are not labelled.

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

a.

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

b.

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

c.

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

a.

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.

b.

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.

c.

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.

[2]
a.

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

[1]
b.

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

[1]
c.

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

[3]
d.
Answer/Explanation

Markscheme

     A1A1

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

[2 marks]

a.

     A1

[1 mark]

b.

     A1

[1 mark]

c.

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]

d.

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

a.

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

b.

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

c.

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.

d.

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.

[2]
a.

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

[1]
b.

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

[1]
c.

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

[3]
d.
Answer/Explanation

Markscheme

     A1A1

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

[2 marks]

a.

     A1

[1 mark]

b.     A1

[1 mark]

c.

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]

d.

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

a.

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

b.

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

c.

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.

d.

Question

A simple connected planar graph, has \(e\) edges, \(v\) vertices and \(f\) faces.

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

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

[6]
a.

(i)     State the handshaking lemma.

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

[4]
b.

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

[2]
c.
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]

a.

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

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

substituting \(v = e\) into Euler’s formula     M1

\(f = 2\)     A1

[4 marks]

b.

for example,

     A2

[2 marks]

Total [12 marks]

c.

Examiners report

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

a.

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

b.

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

c.

Question

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

Show that \(G\) is bipartite.

[2]
a.

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

[1]
b.

In a planar graph the degree of a face is defined as the number of edges adjacent to that face.

(i)     Write down the degree of each of the four faces of \(G\).

(ii)     Explain why the sum of the degrees of all the faces is twice the number of edges.

[2]
c.

\(H\) is a simple connected planar bipartite graph with \(e\) edges, \(f\) faces, \(v\) vertices and \(v \ge 3\).

Explain why there can be no face in \(H\) of degree

(i)     one;

(ii)     two;

(iii)     three.

[3]
d.

Hence prove that for \(H\)

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

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

[3]
e.

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

[2]
f.
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]

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.

Examiners report

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

[N/A]

e.

[N/A]

f.
Scroll to Top