| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2024 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Graph isomorphism |
| Difficulty | Moderate -0.3 This is a straightforward Further Maths Decision question testing basic graph theory concepts: identifying isomorphic trees by comparing degree sequences, drawing a simple tree structure, applying the handshaking lemma (sum of degrees = 2×edges), and recognizing that trees have n-1 edges. The pigeonhole principle application is standard. While it requires understanding of multiple concepts, each part involves direct application of definitions and well-known results without requiring novel insight or complex problem-solving. |
| Spec | 7.02j Isomorphism: of graphs, degree sequences |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (a) | C and D |
| [1] | 1.2 | cao |
| 1 | (b) | B1 |
| [1] | 1.1 | A tree that is isomorphic to this |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (c) | (1+1+1+3+3+3)/2 |
| = 6 | M1 |
| Answer | Marks |
|---|---|
| [2] | 3.1a |
| 1.1 | NOT from a sketch diagram (unless working is also seen) |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (d) | A tree with 6 vertices would have 6 – 1 = 5 |
| edges, but graph G has 6 edges (from part c) | B1 | |
| [1] | 2.4 | Using result from part c to show why G is not a tree |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (e) | Pigeons are the actual degrees of the 6 vertices |
| Answer | Marks |
|---|---|
| degree 0 | B1 |
| Answer | Marks |
|---|---|
| [3] | 2.1 |
| Answer | Marks |
|---|---|
| 2.2a | Identified in any way e.g. 6 pigeons/vertices and 5 degrees |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | 2 | 3 |
| C | E | I |
| 1 | 3 | 0 |
Question 1:
1 | (a) | C and D | B1
[1] | 1.2 | cao
1 | (b) | B1
[1] | 1.1 | A tree that is isomorphic to this
with vertex degrees 1, 1, 1, 1, 2, 4
1 | (c) | (1+1+1+3+3+3)/2
= 6 | M1
A1
[2] | 3.1a
1.1 | NOT from a sketch diagram (unless working is also seen)
Seen or implied from working
6
SC B1 answer 6 without appropriate method
1 | (d) | A tree with 6 vertices would have 6 – 1 = 5
edges, but graph G has 6 edges (from part c) | B1
[1] | 2.4 | Using result from part c to show why G is not a tree
In G the number of edges = the number of vertices, so not a tree
1 | (e) | Pigeons are the actual degrees of the 6 vertices
and pigeonholes (options) are the possible
vertex degrees, but cannot have both 0 and 5
because if any vertex has degree 0 then it is not
joined to the others so max degree is 4 OR
if any vertex has degree 5 it is connected to all
the others so min degree is 1 so no vertex with
degree 0 | B1
M1
A1
[3] | 2.1
1.1
2.2a | Identified in any way e.g. 6 pigeons/vertices and 5 degrees
Vertex degrees cannot be all of {0, 1, 2, 3, 4, 5}
Allow for {1, 2, 3, 4, 5} or {0, 1, 2, 3, 4} seen
Explaining why {0, 1, 2, 3, 4, 5} is not possible and using
pigeonhole principle to conclude result
If graph is assumed to be connected (i.e. assuming 1 to 5 only)
B1 M1 max
1 | 2 | 3 | 0 | 2
C | E | I
1 | 3 | 0 | 0 | 01 There are six non-isomorphic trees with exactly six vertices.\\
A student has drawn the diagram below showing six trees each with exactly six vertices. However, two of the trees that the student has drawn are isomorphic.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_222_243_388_246}
\captionsetup{labelformat=empty}
\caption{A}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_240_392_635}
\captionsetup{labelformat=empty}
\caption{B}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_241_392_1023}
\captionsetup{labelformat=empty}
\caption{C}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_218_246_758_246}
\captionsetup{labelformat=empty}
\caption{D}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_216_243_760_632}
\captionsetup{labelformat=empty}
\caption{E}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{6f64abca-108c-4b81-8ccf-124dfd9cc2f6-2_214_241_762_1023}
\captionsetup{labelformat=empty}
\caption{F}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Identify which two of these trees are isomorphic.
\item Draw an example of the missing tree.
Graph G has exactly six vertices.\\
The degree sequence of G is $1,1,1,3,3,3$.
\item Without using a sketch, calculate the number of edges in graph G.
\item Explain how the result from part (c) shows that graph G is not a tree.
In a simple graph with six vertices each vertex degree must be one of the values $0,1,2,3,4$ or 5 .
\item Use the pigeonhole principle to show that in a simple graph with six vertices there must be at least two vertices with the same vertex degree.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2024 Q1 [8]}}