| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2019 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Graph isomorphism |
| Difficulty | Moderate -0.3 This is a straightforward graph theory question testing basic definitions and properties. Part (a) requires simple counting of vertex degrees, (b) uses degree sequences to prove non-isomorphism (a standard technique), (c) applies Eulerian graph criteria directly from definitions, and (d) involves basic counting of edges between complete graphs. All parts are routine applications of fundamental concepts with no novel problem-solving required, making it slightly easier than average for A-level Further Maths. |
| Spec | 7.02d Complete graphs: K_n and number of arcs7.02g Eulerian graphs: vertex degrees and traversability7.02j Isomorphism: of graphs, degree sequences7.02l Planar graphs: planarity, subdivision, contraction |
| Answer | Marks | Guidance |
|---|---|---|
| Vertex | J | K |
| Degree | 1 | 3 |
| Vertex | P | Q |
| Degree | 3 | 2 |
| M1 (AO 1.1) | Each graph has at least three vertices of degree 2 listed | |
| M1 (AO 1.1) | J and T each have degree 1 | |
| A1 (AO 1.1) | All correct |
| Answer | Marks |
|---|---|
| B1 (AO 1.1) | The region in G1 has four edges (regions have four edges); Incomplete explanation that uses both graphs = B1, B0; e.g. No arc between J and N but P is joined to Q |
| B1 (AO 2.1) | The region in G2 has three edges (regions have three edges); Or equivalent written explanation |
| Answer | Marks | Guidance |
|---|---|---|
| Still (at least one) odd degree | B1 (AO 2.1) | Still have vertices of degree 3; P and/or K not even degrees |
| Answer | Marks | Guidance |
|---|---|---|
| Add an arc joining P to K | B1 (AO 1.1) | P to K, written; Arc PK |
# Question 2:
## Part (a)
| Vertex | J | K | L | M | N |
|--------|---|---|---|---|---|
| Degree | 1 | 3 | 2 | 2 | 2 |
| Vertex | P | Q | R | S | T |
|--------|---|---|---|---|---|
| Degree | 3 | 2 | 2 | 2 | 1 |
| M1 (AO 1.1) | Each graph has at least three vertices of degree 2 listed
| M1 (AO 1.1) | J and T each have degree 1
| A1 (AO 1.1) | All correct
## Part (b)
e.g. In G1, the vertex with degree 3 is connected to the vertex of degree 1 (and two of degree 2). In G2, the vertex of degree 3 is connected to three vertices of degree 2.
e.g. In G1 the vertex of degree 1 is connected to the vertex of degree 3 but in G2 it is connected to a vertex of degree 2.
| B1 (AO 1.1) | The region in G1 has four edges (regions have four edges); Incomplete explanation that uses both graphs = B1, B0; e.g. No arc between J and N but P is joined to Q
| B1 (AO 2.1) | The region in G2 has three edges (regions have three edges); Or equivalent written explanation
## Part (c)(i)
Still (at least one) odd degree | B1 (AO 2.1) | Still have vertices of degree 3; P and/or K not even degrees
## Part (c)(ii)
Add an arc joining P to K | B1 (AO 1.1) | P to K, written; Arc PK2 Two graphs are shown below.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{8473d9aa-a4db-4001-ac71-e5fbbaee530c-2_396_353_1343_479}
\captionsetup{labelformat=empty}
\caption{Graph G1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{8473d9aa-a4db-4001-ac71-e5fbbaee530c-2_399_328_1340_1233}
\captionsetup{labelformat=empty}
\caption{Graph G2}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item List the vertex degrees for each graph.
\item Prove that the graphs are non-isomorphic.
The two graphs are joined together by adding an arc connecting J and T .
\item \begin{enumerate}[label=(\roman*)]
\item Explain how you know that the resulting graph is not Eulerian.
\item Describe how the graph can be made Eulerian by adding one more arc.
The vertices of the graph $K _ { 3 }$ are connected to the vertices of the graph $K _ { 4 }$ to form the graph $K _ { 7 }$.
\end{enumerate}\item Explain why 12 arcs are needed connecting $K _ { 3 }$ to $K _ { 4 }$.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2019 Q2 [10]}}