| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | December |
| Marks | 10 |
| Topic | Graph Theory Fundamentals |
| Type | Graph isomorphism |
| Difficulty | Standard +0.3 This is a structured multi-part question on basic graph theory concepts (vertex degrees, Eulerian paths, isomorphism, Hamiltonian cycles, Euler's formula). While it covers multiple topics, each part requires straightforward application of definitions and standard techniques rather than problem-solving insight. The isomorphism check likely involves comparing simple invariants. Slightly easier than average due to the guided nature and routine application of concepts. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability7.02h Hamiltonian paths: and cycles7.02i Ore's theorem: sufficient condition for Hamiltonian graphs7.02j Isomorphism: of graphs, degree sequences7.02l Planar graphs: planarity, subdivision, contraction7.02m Euler's formula: V + R = E + 2 |
| Answer | Marks | Guidance |
|---|---|---|
| 2 | 3 | 1 |
| n | i | j |
Question 2:
2 | 3 | 1 | 0
n | i | j | d(i, j ) | A | t | m2 Two simply connected graphs are shown below.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_301}
\captionsetup{labelformat=empty}
\caption{Graph 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_1178}
\captionsetup{labelformat=empty}
\caption{Graph 2}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Write down the orders of the vertices for each of these graphs.
\item How many ways are there to allocate these vertex degrees to a graph with vertices $\mathrm { P } , \mathrm { Q }$, $\mathrm { R } , \mathrm { S } , \mathrm { T }$ and U ?
\item Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
\end{enumerate}\item Show that graphs 1 and 2 are not isomorphic.
\item \begin{enumerate}[label=(\roman*)]
\item Write down a Hamiltonian cycle for graph 1.
\item Use Euler's formula to determine the number of regions for graph 1.
\item Identify each of these regions for graph 1 by listing the cycle that forms its boundary.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q2 [10]}}