| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2021 |
| Session | November |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Bipartite graph properties |
| Difficulty | Moderate -0.3 This is a Further Maths Decision Mathematics question, but it tests fundamental graph theory concepts (recognizing K_{2,3}, checking isomorphism by degree sequences, understanding graph thickness) that are largely definitional and procedural. Parts (a)-(c) require recall of definitions and straightforward verification, while part (d) is a mechanical algorithm application. Slightly easier than average A-level standard due to its routine nature. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02j Isomorphism: of graphs, degree sequences7.02m Euler's formula: V + R = E + 27.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions7.02o Thickness: of graphs |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (a) | Graph A |
| Answer | Marks | Guidance |
|---|---|---|
| but in graph A the two vertices of degree 3 are adjacent | B1 | 2.4 |
| Answer | Marks | Guidance |
|---|---|---|
| 2,3 | B1 | 2.4 |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (b) | B1 |
| [1] | 1.1 | A graph that is isomorphic to this |
| 4 | (c) | By Kuratowski’s theorem, K is non-planar, so thickness 2 |
| Answer | Marks |
|---|---|
| Hence thickness = 2 | B1 |
| Answer | Marks |
|---|---|
| [3] | 2.5 |
| Answer | Marks |
|---|---|
| 2.1 | Kuratowski, K is non-planar |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (d) | Not bipartite, two adjacent vertices both coloured |
| Answer | Marks |
|---|---|
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 1.1 | If more than one diagram is used mark the final diagram |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (e) | 1 |
| [1] | 1.1 | cao |
| 4 | (f) | Linear or O(n) |
| [1] | 2.2a | Not n, n – 1, 1𝑛 or 1(𝑛−1) or similar (which is T(n)) |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (g) | 1000 (60 10) = 6000 |
| [1] | 2.2b | correct or follow through order from part (f) |
| 4 | (h) | O(n) O(2n) hierarchy of orders |
| [1] | 2.4 | 26000 21000 > 6, or equivalent |
| 4 | 0 | -2 |
Question 4:
4 | (a) | Graph A
K is a bipartite graph with 2 vertices in one set and 3 in the other so the
2,3
two vertices of degree 3 are not adjacent
but in graph A the two vertices of degree 3 are adjacent | B1 | 2.4 | ‘A’ and an appropriate comment about adjacency of
vertices with the same degree or cycle lengths in A
Description of K may be implied
2,3
Alternative method 1
Graph A
K is a bipartite graph with 2 vertices in one set and 3 in the other so none
2,3
of the three vertices of degree 2 are adjacent
but in graph A the two of the vertices of degree 2 are adjacent
Alternative method 2
Graph A
K is a bipartite graph so cycles are of even length (length 4)
2,3
but in graph A there is a cycle of length 3 (or of length 5)
Graph C
K has 5 vertices and 6 arcs
2,3
but graph C has 8 arcs so not isomorphic to K
2,3 | B1 | 2.4 | ‘C’ and an appropriate comment about number of
arcs or degrees of vertices or cycle lengths
Description of K may be implied
2,3
Alternative method 1
Graph C
Degree sequence for K is 2, 2, 2, 3, 3
2,3
but graph C has no vertices of degree 2 (or has a vertex of degree 4)
Alternative method 2
Graph C
K is a bipartite graph so cycles are of even length (length 4)
2,3
but in graph C there are cycles of length 3 (or of length 5)
[2]
4 | (b) | B1
[1] | 1.1 | A graph that is isomorphic to this
4 | (c) | By Kuratowski’s theorem, K is non-planar, so thickness 2
5
K = K + G
5 2, 3
from part (a), both of these are planar so thickness 2
Hence thickness = 2 | B1
M1
A1
[3] | 2.5
3.1a
2.1 | Kuratowski, K is non-planar
5
Partitioning K as two planar graphs, eg K and G
5 2, 3
and attempt to explain that each of these is planar
Complete reasoning
4 | (d) | Not bipartite, two adjacent vertices both coloured | M1
A1
A1
[3] | 1.1
1.1
1.1 | If more than one diagram is used mark the final diagram
Top left = , top right and bottom left =
Bottom right and centre =
Correct conclusion with reason (step 5 of algorithm)
4 | (e) | 1 | B1
[1] | 1.1 | cao
4 | (f) | Linear or O(n) | B1
[1] | 2.2a | Not n, n – 1, 1𝑛 or 1(𝑛−1) or similar (which is T(n))
2 2
4 | (g) | 1000 (60 10) = 6000 | B1ft
[1] | 2.2b | correct or follow through order from part (f)
4 | (h) | O(n) O(2n) hierarchy of orders | B1
[1] | 2.4 | 26000 21000 > 6, or equivalent
4 | 0 | -24 One of these graphs is isomorphic to $\mathrm { K } _ { 2,3 }$.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_175_195_285_242}
\captionsetup{labelformat=empty}
\caption{Graph A}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_170_195_285_635}
\captionsetup{labelformat=empty}
\caption{Graph B}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_168_191_287_1027}
\captionsetup{labelformat=empty}
\caption{Graph C}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Explain how you know that each of the other graphs is not isomorphic to $\mathrm { K } _ { 2,3 }$.
The arcs of the complete graph $\mathrm { K } _ { 5 }$ can be partitioned as the complete bipartite graph $\mathrm { K } _ { 2,3 }$ and a graph G.
\item Draw the graph G.
\item Explain carefully how you know that the graph $\mathrm { K } _ { 5 }$ has thickness 2 .
The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, $\alpha$ and $\beta$.
STEP 1 Choose a vertex and assign it colour $\alpha$.\\
STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour $\beta$ to each vertex that is adjacent to a vertex with colour $\alpha$.
STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour $\alpha$ to each vertex that is adjacent to a vertex with colour $\beta$.
STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.\\
STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite.
STEP 6 Stop.
\item Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not.
A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
\item Write down how many passes through STEP 4 are needed for the bipartite graph $\mathrm { K } _ { 2,3 }$.
The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
\item What can you deduce about the efficiency of the colouring algorithm in this worst case?
The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
\item Estimate the number of vertices in graph Y .
A different algorithm has efficiency $\mathrm { O } \left( 2 ^ { n } \right)$. This algorithm takes 10 seconds to run for graph X .
\item Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2021 Q4 [13]}}