Question
The graph G has the following cost adjacency table.
\[\begin{array}{*{20}{c|ccccc}}
{}&{\text{A}}&{\text{B}}&{\text{C}}&{\text{D}}&{\text{E}} \\
\hline
{\text{A}}& {\text{ – }}&9&{\text{ – }}&8&4 \\
{\text{B}}& 9&{\text{ – }}&7&{\text{ – }}&2 \\
{\text{C}}& {\text{ – }}&7&{\text{ – }}&7&3 \\
{\text{D}}& 8&{\text{ – }}&7&{\text{ – }}&5 \\
{\text{E}}& 4&2&3&5&{\text{ – }}
\end{array}\]
Draw G in a planar form.
Giving a reason, determine the maximum number of edges that could be added to G while keeping the graph both simple and planar.
List all the distinct Hamiltonian cycles in G beginning and ending at A, noting that two cycles each of which is the reverse of the other are to be regarded as identical. Hence determine the Hamiltonian cycle of least weight.
Answer/Explanation
Markscheme
A2
[2 marks]
For a simple planar graph containing triangles, \(e \leqslant 3v – 6\) M1
Here \(v = 5{\text{ , so }}e \leqslant 9\) . A1
There are already 8 edges so the maximum number of edges that could be added is 1. R1
This can be done e.g. AC or BD R1
[4 marks]
The distinct Hamiltonian cycles are
ABCDEA A2
ABCEDA A2
ABECDA A2
AEBCDA A2
Note: Do not penalise extra cycles.
The weights are 32, 32, 29, 28 respectively. A1
The Hamiltonian cycle of least weight is AEBCDA. R1
[10 marks]
Examiners report
A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.
A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.
A fairly common error in (a) was to draw a non-planar version of G, for which no credit was given. In (b), most candidates realised that only one extra edge could be added but a convincing justification was often not provided. Most candidates were reasonably successful in (c) although in some cases not all possible Hamiltonian cycles were stated.
Question
Prove that a graph containing a triangle cannot be bipartite.
Prove that the number of edges in a bipartite graph with n vertices is less than or equal to \(\frac{{{n^2}}}{4}\).
Answer/Explanation
Markscheme
At least two of the three vertices in the triangle must lie on one of the two disjoint sets M1R1
These two are joined by an edge so the graph cannot be bipartite R1
[3 marks]
If there are x vertices in one of the two disjoint sets then there are (n – x) vertices in the other disjoint set M1
The greatest number of edges occurs when all vertices in one set are joined to all vertices in the other to give x(n – x) edges A1
Function f(x) = x(n – x) has a parabolic graph. M1
This graph has a unique maximum at \(\left( {\frac{n}{2},\frac{{{n^2}}}{4}} \right)\). A1
so \(x(n – x) \leqslant \frac{{{n^2}}}{4}\) R1
[5 marks]
Examiners report
Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.
Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.
Question
(a) A connected planar graph G has e edges and v vertices.
(i) Prove that \(e \geqslant v – 1\).
(ii) Prove that e = v −1 if and only if G is a tree.
(b) A tree has k vertices of degree 1, two of degree 2, one of degree 3 and one of degree 4. Determine k and hence draw a tree that satisfies these conditions.
(c) The graph H has the adjacency table given below.
\[\left( {\begin{array}{*{20}{c}}
0&1&1&0&0&0 \\
1&0&0&1&1&0 \\
1&0&0&0&1&1 \\
0&1&0&0&0&0 \\
0&1&1&0&0&0 \\
0&0&1&0&0&0
\end{array}} \right)\]
(i) Explain why H cannot be a tree.
(ii) Draw the graph of H .
(d) Prove that a tree is a bipartite graph.
Answer/Explanation
Markscheme
(a) (i) Euler’s relation is
\(e = v – 2 + f \geqslant v – 1,{\text{ as }}f \geqslant 1\) M1A1
(ii) \(G{\text{ is a tree }} \Leftrightarrow {\text{ no cycles }} \Leftrightarrow {\text{ }}f = 1\) R1R1
[4 marks]
(b) the result from (a) (ii) gives
\(e = k + 2 + 1 + 1 – 1 = k + 3\) M1A1
for a tree we also have
\(2e = {\text{sum of degrees}}\) M1
\(2k + 6 = k + 4 + 3 + 4 = k + 11\)
hence \(k = 5\) A1
A2
Note: Accept alternative correct solutions.
[6 marks]
(c) (i) \(v – 1 = 5 < 6 = e\,\,\,\,\,{\text{by (a) (ii)}}\) M1A1
G cannot be a tree AG
(ii) A1
[3 marks]
(d) take any vertex in the tree and colour it black M1
colour all adjacent vertices white
colour all vertices adjacent to a white vertex black
continue this procedure until all vertices are coloured M1
which must happen since the graph is connected R1
as the tree contains no cycles, no vertex can be both black and white and the graph is proved to be bipartite R1
[4 marks]
Total [17 marks]
Examiners report
Many candidates seem only to have a weak understanding of the requirements for the proof of a mathematical statement.
Question
The planar graph G and its complement \(G’\) are both simple and connected.
Given that G has 6 vertices and 10 edges, show that \(G’\) is a tree.
Answer/Explanation
Markscheme
the complete graph with 6 vertices has 15 edges so \(G’\) has
6 vertices and 5 edges M1A1
the number of faces in \(G’\) , \(f = 2 + e – v = 1\) M1A1
it is therefore a tree because \(f = 1\) R1
Note: Accept it is a tree because \(v = e + 1\)
[5 marks]
Examiners report
Part (a) was well answered by many candidates.
Question
Show that a graph is bipartite if and only if it contains only cycles of even length.
Answer/Explanation
Markscheme
Suppose the graph is bipartite so that the vertices belong to one of two disjoint sets M, N. M1
Then consider any vertex V in M. To generate a cycle returning to V, we must go to a vertex in N, then to a vertex in M, then to a vertex in N, then to a vertex in M, etc. R1
To return to V, therefore, which belongs to M, an even number of steps will be required. R1
Now suppose the graph contains only cycles of even length. M1
Starting at any vertex V, define the set M as containing those vertices accessible from V in an even number of steps and the set N as containing those vertices accessible from V in an odd number of steps. R1
Suppose that the vertex X belongs to both M and N. Then consider the closed walk from V to X one way and back to V the other way. This closed walk will be of odd length. This closed walk can be contracted to a cycle which will also be of odd length, giving a contradiction to the initial assumption. R1
There can therefore be no vertices common to M and N which shows that the vertices can be divided into two disjoint sets and the graph is bipartite. R1
Consider any edge joining P to vertex Q. Then either \({\text{P}} \in {\text{M}}\) in which case \({\text{Q}} \in {\text{M}}\) or vice versa. In either case an edge always joins a vertex in M to a vertex in N so the graph is bipartite. R1
[8 marks]
Examiners report
Many candidates made a reasonable attempt at showing that bipartite implies cycles of even length but few candidates even attempted the converse.
Question
(a) Show that, for a connected planar graph,
\[v + f – e = 2.\]
(b) Assuming that \(v \geqslant 3\), explain why, for a simple connected planar graph, \(3f \leqslant 2e\) and hence deduce that \(e \leqslant 3v – 6\).
(c) The graph G and its complement \({G’}\) are simple connected graphs, each having 12 vertices. Show that \({G}\) and \({G’}\) cannot both be planar.
Answer/Explanation
Markscheme
(a) start with a graph consisting of just a single vertex M1
for this graph, v = 1, f = 1 and e = 0, the relation is satisfied A1
Note: Allow solutions that begin with 2 vertices and 1 edge.
to extend the graph you either join an existing vertex to another existing vertex which increases e by 1 and f by 1 so that v + f – e remains equal to 2 M1A1
or add a new vertex and a corresponding edge which increases e by 1 and v by 1 so that v + f – e remains equal to 2 M1A1
therefore, however we build up the graph, the relation remains valid R1
[7 marks]
(b) since every face is bounded by at least 3 edges, the result follows by counting up the edges around each face R1
the factor 2 follows from the fact that every edge bounds (at most) 2 faces R1
hence \(3f \leqslant 2e\) AG
from the Euler relation, \(3f = 6 + 3e – 3v\) M1
substitute in the inequality, \(6 + 3e – 3v \leqslant 2e\) A1
hence \(e \leqslant 3v – 6\) AG
[4 marks]
(c) let G have e edges M1
since G and \({G’}\) have a total of \(\left( {\begin{array}{*{20}{c}}
{12} \\
2
\end{array}} \right) = 66\) edges A1
it follows that \({G’}\) has 66 – e edges A1
for planarity we require
\(e \leqslant 3 \times 12 – 6 = 30\) M1A1
and \(66 – e \leqslant 30 \Rightarrow e \geqslant 36\) A1
these two inequalities cannot both be met indicating that both graphs cannot be planar R1
[7 marks]
Total [18 marks]
Examiners report
Parts (a) and (b) were found difficult by many candidates with explanations often inadequate. In (c), candidates who realised that the union of a graph with its complement results in a complete graph were often successful.
Question
The vertices of a graph L are A, B, C, D, E, F, G and H. The weights of the edges in L are given in the following table.
Draw the graph L.
Answer/Explanation
Markscheme
A2
Note: Award A1 if one line missing or one line misplaced. Weights are not required.
[2 marks]
Examiners report
Most candidates were able to draw the graph as required in (a) and most made a meaningful start to applying Prim’s algorithm in (b). Candidates were not always clear about the order in which the edges were to be added.
Question
The graph G has adjacency matrix M given below.
Draw the graph G .
What information about G is contained in the diagonal elements of M\(^2\) ?
List the trails of length 4 starting at A and ending at C.
Answer/Explanation
Markscheme
A2
Note: Award A1 if only one error, A0 for two or more.
[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; A1A1A0 for all correct, but with additions; A1A0A0 for two correct with or without additions.
[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 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.
Answer/Explanation
Markscheme
as a first step, form the following graph
(M1)(A1)
make it planar
A1
[3 marks]
(i) an edge joins a pair of vertices R1
there is a maximum of \(\left( {\begin{array}{*{20}{c}}
v \\
2
\end{array}} \right) = \frac{1}{2}v(v – 1)\) possible unordered pairs of vertices, hence displayed result A1AG
(ii) an edge joins two vertices in \({G’}\) if it does not join them in G and vice versa; all possible edges are accounted for by the union of the two graphs R1
\(e + e’ = \frac{1}{2}v(v – 1)\) A1
(iii) the two graphs have the same number of edges R1
\( \Rightarrow e = \frac{1}{4}v(v – 1)\) A1
v and v – 1 are consecutive integers, so only one can be divisible by 4, hence displayed result A1AG
(iv) the required graphs have four vertices and three edges A1
if one vertex is adjacent to the other three, that uses up the edges; the resulting graph, necessarily connected, has a disconnected complement, and vice versa R1
if one vertex is adjacent to two others, that uses up two edges; the final vertex cannot be adjacent to the first; the result is the linear connected graph A1
state it is isomorphic to its complement A1 N2
Note: Alternative proofs are possible, but should include the final statement for full marks.
(v) using \(e \leqslant 3v – 6\) for planar graphs M1
\(\frac{1}{2}v(v – 1) = e + e’ \leqslant 6v – 12\) A1
\({v^2} – 13v + 24 \leqslant 0\) is not possible for \(v \geqslant 11\) R1
[14 marks]
Examiners report
Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.
Part (a) was well done. The various parts of Parts (b) were often attempted, but with a disappointing feeling that the candidates did not have a confident understanding of what they were writing.
Question
Draw the complement of the following graph as a planar graph.
A simple graph G has v vertices and e edges. The complement \(G’\) of G has \({e’}\) edges.
(i) Prove that \(e \leqslant \frac{1}{2}v(v – 1)\) .
(ii) Find an expression for \(e + e’\) in terms of v .
(iii) Given that \({G’}\) is isomorphic to G , prove that v is of the form 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.
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
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 weights of the edges of a graph \(H\) are given in the following table.
(i) Draw the weighted graph \(H\).
(ii) Use Kruskal’s algorithm to find the minimum spanning tree of \(H\). Your solution should indicate the order in which the edges are added.
(iii) State the weight of the minimum spanning tree.
Consider the following weighted graph.
(i) Write down a solution to the Chinese postman problem for this graph.
(ii) Calculate the total weight of the solution.
(i) State the travelling salesman problem.
(ii) Explain why there is no solution to the travelling salesman problem for this graph.
Answer/Explanation
Markscheme
(i) A2
Note: Award A1 if one edge is missing. Award 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]
(i) eg, \(PQRSRTSTQP\) OR \(PQTSTRSRQP\) M1A1
Note: Award M1 if in either (i) or (ii), it is recognised that edge \(PQ\) is needed twice.
(ii) total weight \( = 34\) A1
[3 marks]
(i) to determine a cycle where each vertex is visited once only (Hamiltonian cycle) A1
of least total weight A1
(ii) EITHER
to reach \(P\), \(Q\) must be visited twice which contradicts the definition of the \(TSP\) R1
OR
the graph is not a complete graph and hence there is no solution to the \(TSP\) R1
[3 marks]
Total [14 marks]
Examiners report
Part (a) was generally very well answered. Most candidates were able to correctly sketch the graph of \(H\) and apply Kruskal’s algorithm to determine the minimum spanning tree of \(H\). A few candidates used Prim’s algorithm (which is no longer part of the syllabus).
Most candidates understood the Chinese Postman Problem in part (b) and knew to add the weight of \(PQ\) to the total weight of \(H\). Some candidates, however, did not specify a solution to the Chinese Postman Problem while other candidates missed the fact that a return to the initial vertex is required.
In part (c), many candidates had trouble succinctly stating the Travelling Salesman Problem. Many candidates used an ‘edge’ argument rather than simply stating that the Travelling Salesman Problem could not be solved because to reach vertex \(P\), vertex \(Q\) had to be visited twice.
Question
The graph \({K_{2,{\text{ }}2}}\) is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.
Draw \({K_{2,{\text{ }}2}}\) as a planar graph.
Draw a spanning tree for \({K_{2,{\text{ }}2}}\).
Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).
Show that the complement of any complete bipartite graph does not possess a spanning tree.
Answer/Explanation
Markscheme
A1A1
Note: Award A1 for a correct version of \({K_{2,{\text{ }}2}}\) and A1 for a correct planar representation.
[2 marks]
A1
[1 mark]
A1
[1 mark]
the complete bipartite graph \({K_{m,{\text{ }}n}}\) has two subsets of vertices \(A\) and \(B\), such that each element of \(A\) is connected to every element of \(B\) A1
in the complement, no element of \(A\) is connected to any element of \(B\). The complement is not a connected graph A1
by definition a tree is connected R1
hence the complement of any complete bipartite graph does not possess a spanning tree AG
[3 marks]
Total [7 marks]
Examiners report
Part (a) was generally well done with a large number of candidates drawing a correct planar representation for \({K_{2,2}}\). Some candidates, however, produced a correct non-planar representation of \({K_{2,2}}\).
Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).
Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).
Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of \({K_{m,n}}\) does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.
Question
The graph \({K_{2,{\text{ }}2}}\) is the complete bipartite graph whose vertex set is the disjoint union of two subsets each of order two.
Draw \({K_{2,{\text{ }}2}}\) as a planar graph.
Draw a spanning tree for \({K_{2,{\text{ }}2}}\).
Draw the graph of the complement of \({K_{2,{\text{ }}2}}\).
Show that the complement of any complete bipartite graph does not possess a spanning tree.
Answer/Explanation
Markscheme
A1A1
Note: Award A1 for a correct version of \({K_{2,{\text{ }}2}}\) and A1 for a correct planar representation.
[2 marks]
A1
[1 mark]
[1 mark]
the complete bipartite graph \({K_{m,{\text{ }}n}}\) has two subsets of vertices \(A\) and \(B\), such that each element of \(A\) is connected to every element of \(B\) A1
in the complement, no element of \(A\) is connected to any element of \(B\). The complement is not a connected graph A1
by definition a tree is connected R1
hence the complement of any complete bipartite graph does not possess a spanning tree AG
[3 marks]
Total [7 marks]
Examiners report
Part (a) was generally well done with a large number of candidates drawing a correct planar representation for \({K_{2,2}}\). Some candidates, however, produced a correct non-planar representation of \({K_{2,2}}\).
Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).
Parts (b) and (c) were generally well done with many candidates drawing a correct spanning tree for \({K_{2,2}}\) and the correct complement of \({K_{2,2}}\).
Part (d) tested a candidate’s ability to produce a reasoned argument that clearly explained why the complement of \({K_{m,n}}\) does not possess a spanning tree. This was a question part in which only the best candidates provided the necessary rigour in explanation.
Question
A simple connected planar graph, has \(e\) edges, \(v\) vertices and \(f\) faces.
(i) Show that \(2e \ge 3f{\text{ if }}v > 2\).
(ii) Hence show that \({K_5}\), the complete graph on five vertices, is not planar.
(i) State the handshaking lemma.
(ii) Determine the value of \(f\), if each vertex has degree \(2\).
Draw an example of a simple connected planar graph on \(6\) vertices each of degree \(3\).
Answer/Explanation
Markscheme
(i) METHOD 1
attempting to use \(f = e – v + 2\) and \(e \le 3v – 6\) (if \(v > 2\)) (M1)
\(2e \le 6v – 12 = 6(e – f + 2) – 12\) M1A1
leading to \(2e \ge 3f\) AG
METHOD 2
each face is bounded by at least three edges A1
Note: Award A1 for stating \(e \ge 3f\).
each edge either separates two faces or, if an edge is interior to a face, it gets counted twice R1
Note: Award R1 for stating that each edge contributes two to the sum of the degrees of the faces (or equivalent) ie, \(\sum {\deg (F) = 2e} \).
adding up the edges around each face R1
leading to \(2e \ge 3f\) AG
(ii) \({K_5}\) has \(e = 10\) A1
if the graph is planar, \(f = 7\) A1
this contradicts the inequality obtained above R1
hence the graph is non-planar AG
[6 marks]
(i) the sum of the vertex degrees \( = 2e\) (or is even) or equivalent A1
(ii) if each vertex has degree \(2\), then \(2v = 2e\) A1
substituting \(v = e\) into Euler’s formula M1
\(f = 2\) A1
[4 marks]
for example,
A2
[2 marks]
Total [12 marks]
Examiners report
In part (a) (i), many candidates tried to prove \(2e \ge 3f\) with numerical examples. Only a few candidates were able to prove this inequality correctly. In part (a) (ii), most candidates knew that \({K_5}\) has 10 edges. However, a number of candidates simply drew a diagram with any number of faces and used this particular representation as a basis for their ‘proof’. Many candidates did not recognise the ‘hence’ requirement in part (a) (ii).
In part (b) (i), many candidates stated the ‘handshaking lemma’ incorrectly by relating it to the ‘handshake problem’. In part (b) (ii), only a few candidates determined that \(v = e\) and hence found that \(f = 2\).
In part (c), a reasonable number of candidates were able to draw a simple connected planar graph on \(6\) vertices each of degree \(3\). The most common error here was to produce a graph that contained a multiple edge(s).
Question
The following diagram shows the graph \(G\).
Show that \(G\) is bipartite.
State which two vertices should be joined to make \(G\) equivalent to \({K_{3,{\text{ }}3}}\).
In a planar graph the degree of a face is defined as the number of edges adjacent to that face.
(i) Write down the degree of each of the four faces of \(G\).
(ii) Explain why the sum of the degrees of all the faces is twice the number of edges.
\(H\) is a simple connected planar bipartite graph with \(e\) edges, \(f\) faces, \(v\) vertices and \(v \ge 3\).
Explain why there can be no face in \(H\) of degree
(i) one;
(ii) two;
(iii) three.
Hence prove that for \(H\)
(i) \(e \ge 2f\);
(ii) \(e \le 2v – 4\).
Hence prove that \({K_{3,{\text{ }}3}}\) is not planar.
Answer/Explanation
Markscheme
shading alternate vertices or attempting to list pairs M1
EITHER
A1
OR
\(ADE\) and \(BCF\) A1
as no two equal shadings are adjacent, the graph is bipartite AG
[2 marks]
\(C\) and \(E\) A1
[1 mark]
(i) degree of each of the four faces is \(4\) A1
(ii) each edge bounds two faces R1
[2 marks]
(i) simple so no loops R1
(ii) simple so no multiple edges (and \(v > 2\)) R1
(iii) bipartite graph so no triangles R1
[3 marks]
(i) \(2e = \sum {\deg (f) \ge 4f} \) R1
\(e \ge 2f\) AG
(ii) if \(H\) is a simple connected planar graph then \(e + 2 = v + f\) M1
\(e + 2 – v \le \frac{1}{2}e\) M1
\(2e + 4 – 2v \le e\)
\(e \le 2v – 4\) AG
[3 marks]
for \({K_{3,{\text{ }}3}}{\text{ }}v = 6\), and \(e = 9\) A1
\(9 \le 2 \times 6 – 4\) is not true, therefore \({K_{3,{\text{ }}3}}\) cannot be planar R1AG
[2 marks]
Total [13 marks]
Examiners report
[N/A]
[N/A]
[N/A]
[N/A]
[N/A]
[N/A]