| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2019 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Graph isomorphism |
| Difficulty | Standard +0.8 This Further Maths question requires proving graph isomorphism (finding explicit vertex correspondence), applying Euler's formula, and demonstrating understanding of planarity through K5 and K3,3 constructions. While systematic, it demands multiple graph theory concepts and careful reasoning beyond standard A-level, placing it moderately above average difficulty. |
| Spec | 7.02j Isomorphism: of graphs, degree sequences7.02m Euler's formula: V + R = E + 27.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | (a) | (i) |
| Answer | Marks |
|---|---|
| E ↔ T (or S) | B1 |
| B1 | 2.1 |
| 2.1 | A ↔ R, B ↔ Q, D ↔ P |
| Answer | Marks |
|---|---|
| (Or any three correct = B1 only) | May use any symbol to |
| Answer | Marks |
|---|---|
| (ii) | V + R = E + 2 |
| Answer | Marks |
|---|---|
| Regions ABC, ABE, ACBE R = 3 | B1 |
| B1 | 1.2 |
| 2.1 | Sub V = 5 and E = 6 into formula |
| Answer | Marks |
|---|---|
| equivalent | Need evidence of calculation |
| Answer | Marks |
|---|---|
| (b) | Make K by adding arcs |
| Answer | Marks |
|---|---|
| AD, CD, CE, DE | M1 |
| A1 | 2.4 |
| 1.1 | K or arc AD |
| Answer | Marks |
|---|---|
| All correct | Allow G2 used |
| (c) | Make K (with an extra arc) by adding vertex U |
| Answer | Marks |
|---|---|
| and arcs PR, PU, SU, TU | M1 |
| A1 | 2.4 |
| 1.1 | K (as a subgraph) or arc PR |
| Answer | Marks |
|---|---|
| All correct | Allow G1 used |
| Answer | Marks | Guidance |
|---|---|---|
| 1 | -2 | 0 |
| 1 | 0 | 3 |
Question 1:
1 | (a) | (i) | A ↔ R
B ↔ Q
C ↔ S (or T)
D ↔ P
E ↔ T (or S) | B1
B1 | 2.1
2.1 | A ↔ R, B ↔ Q, D ↔ P
C ↔ S and E ↔ T
(Or any three correct = B1 only) | May use any symbol to
indicate correspondence
Or a reasoned argument or
shown in a diagram
(ii) | V + R = E + 2
5 + R = 6 + 2 ⇒ R = 3
Vertices A, B, C, D, E V = 5
Edges AB, AC, AE, BC, BD, BE E = 6
Regions ABC, ABE, ACBE R = 3 | B1
B1 | 1.2
2.1 | Sub V = 5 and E = 6 into formula
or 5 + 3 = 6 + 2 or equivalent
Describing the three regions by
listing vertices or ‘ABC, ABE and
outside region (infinite region)’ or
equivalent | Need evidence of calculation
not just R = 3
Vertices in any order (e.g.
ABCE for ACBE) allow
inclusion of D and repeats
(e.g. ACBDBEA for
ACBEA)
(b) | Make K by adding arcs
5
AD, CD, CE, DE | M1
A1 | 2.4
1.1 | K or arc AD
5
All correct | Allow G2 used
(c) | Make K (with an extra arc) by adding vertex U
3,3
and arcs PR, PU, SU, TU | M1
A1 | 2.4
1.1 | K (as a subgraph) or arc PR
3,3
All correct | Allow G1 used
[8]
1 | -2 | 0 | 1 | 0 | 0 | 0
1 | 0 | 3 | 5 | 0 | 1 | 601 Two graphs are shown below.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_396_351_397_246}
\captionsetup{labelformat=empty}
\caption{Graph G1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_394_343_397_932}
\captionsetup{labelformat=empty}
\caption{Graph G2}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Prove that the graphs are isomorphic.
\item Verify that Euler's formula holds for graph G1.
\end{enumerate}\item Describe how it is possible to add 4 arcs to graph G1 to make a non-planar graph with 5 vertices.
\item Describe how it is possible to add a vertex U and 4 arcs to graph G 2 to make a connected nonplanar graph with 6 vertices.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2019 Q1 [8]}}