| Exam Board | OCR |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2017 |
| Session | Specimen |
| Marks | 6 |
| Topic | Graph Theory Fundamentals |
| Type | Eulerian classification |
| Difficulty | Moderate -0.3 This is a straightforward application of standard graph theory definitions from AS Further Maths. Parts (i)-(iii) require direct recall of Eulerian criteria and basic definitions (semi-Eulerian means exactly 2 odd vertices, non-simple means loops/multiple edges). Part (iv) requires slightly more thought about isomorphism but the vertex degree sequences being identical makes this a routine check of local structure. The question is slightly easier than average A-level due to being mostly definitional recall with minimal problem-solving. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.02j Isomorphism: of graphs, degree sequences |
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]{da50ab63-a6f5-4533-ba6d-f9941b71038f-03_602_611_360_280}
\captionsetup{labelformat=empty}
\caption{Graph 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{da50ab63-a6f5-4533-ba6d-f9941b71038f-03_420_499_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 FD1 AS 2017 Q4 [6]}}