| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Session | Specimen |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Eulerian classification |
| Difficulty | Moderate -0.3 This is a straightforward application of standard graph theory definitions (semi-Eulerian paths, simple graphs, isomorphism) with minimal problem-solving required. Parts (i)-(iii) involve direct recall and observation, while part (iv) requires basic comparison of vertex properties. Slightly easier than average due to the guided nature and routine application of well-defined criteria. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.02j Isomorphism: of graphs, degree sequences |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (i) | Route e.g. c – b – a – e – d – c – b – e – d |
| [1] | 1.1 | A route nthat starts and ends at c and d |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (ii) | It has exactly two odd vertex orders |
| [1] | 1.2 | e |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (iii) | In graph 1 there are two arcs directly joining b to |
| Answer | Marks |
|---|---|
| w | B1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| Answer | Marks |
|---|---|
| c1.1 | m |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (iv) | e.g. in graph 1 the vertex of degree 2 (a) is |
| Answer | Marks |
|---|---|
| only has one such pair (vw) | e |
| Answer | Marks |
|---|---|
| [2] | 2.3 |
| 1.1 | Partially correct explanation of why the |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | 0 | 0 |
| 4 | 5 | 6 |
| Answer | Marks |
|---|---|
| 4(i) | e |
| Answer | Marks |
|---|---|
| 4(ii) | i |
| Answer | Marks |
|---|---|
| 4(iii) | p |
Question 4:
4 | (i) | Route e.g. c – b – a – e – d – c – b – e – d | B1
[1] | 1.1 | A route nthat starts and ends at c and d
and uses every edge once and only
once
4 | (ii) | It has exactly two odd vertex orders | B1
[1] | 1.2 | e
Two and only two odd
4 | (iii) | In graph 1 there are two arcs directly joining b to
c (or d to e)
In graph 2 there are two arcs directly joining v to
w | B1
B1
[2] | 1.1
i
c1.1 | m
Reason why graph 1 is not simple
Reason why graph 2 is not simple
4 | (iv) | e.g. in graph 1 the vertex of degree 2 (a) is
adjacent to each vertex of degree 4 (b pand e),
whereas in graph 2 the vertex of degree 2 (y) is
adjacent to one vertex of degreSe 4 (z) but not the
other (w)
e.g. graph 1 has two pairs of vertices directly
joined by two arcs (bc and de) whereas graph 2
only has one such pair (vw) | e
M1
A1
[2] | 2.3
1.1 | Partially correct explanation of why the
graphs are not isomorphic
Fully correct explanation
4 | 0 | 0 | 8.00
4 | 5 | 6 | - | 5
--- 4(i) ---
4(i) | e
m
--- 4(ii) ---
4(ii) | i
c
e
--- 4(iii) ---
4(iii) | p
S
--- 4(iv) ---
4(iv)4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4 .
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a6800c9f-583b-493a-906c-015df63b842f-3_605_616_360_278}
\captionsetup{labelformat=empty}
\caption{Graph 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a6800c9f-583b-493a-906c-015df63b842f-3_420_501_497_1169}
\captionsetup{labelformat=empty}
\caption{Graph 2}
\end{center}
\end{figure}
(i) Write down a semi-Eulerian route for graph 1 .\\
(ii) Explain how the vertex orders show that graph 2 is also semi-Eulerian.\\
(iii) By referring to specific vertices, explain how you know that these graphs are not simple.\\
(iv) By referring to specific vertices, explain how you know that these graphs are not isomorphic.
\hfill \mbox{\textit{OCR Further Discrete AS Q4 [6]}}