| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Year | 2023 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Adjacency matrix interpretation |
| Difficulty | Standard +0.3 This is a straightforward Further Maths question testing basic graph theory definitions and adjacency matrix interpretation. Part (a) requires recall of Eulerian graph properties and simple counting, while part (b) involves reading an adjacency matrix and finding an Eulerian trail—all standard textbook exercises with no novel problem-solving required. The multi-part structure adds length but not conceptual difficulty. |
| Spec | 7.02d Complete graphs: K_n and number of arcs7.02e Bipartite graphs: K_{m,n} notation7.02g Eulerian graphs: vertex degrees and traversability7.02k Digraphs: directed graphs, indegree and outdegree |
| A | B | C | D | |
| A | 0 | 1 | 0 | 1 |
| B | 0 | 0 | 2 | 0 |
| C | 2 | 1 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
| Answer | Marks |
|---|---|
| 4 | 9 |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | 9 | |
| 4 | (a) | (i) |
| Answer | Marks |
|---|---|
| degree so there is a contradiction | B1 |
| Answer | Marks |
|---|---|
| [2] | 2.4 |
| 2.4 | Complete (or K ) degree 3, allow odd |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (a) | (ii) |
| Answer | Marks |
|---|---|
| Hence each vertex of G has degree 2 | B1 |
| Answer | Marks |
|---|---|
| [2] | 2.2a |
| 2.4 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (a) | (iii) |
| Answer | Marks | Guidance |
|---|---|---|
| to form the two sets. | B1 | |
| [1] | 1.1 | Showing that G is bipartite (no FT) |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (b) | (i) |
| [1] | 2.2a | No arcs for each vertex to itself |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (b) | (ii) |
| [1] | 2.2a | 1+ 1+ … = 10 or 2 + 2 + 4 + 2 = 10, or similar |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (b) | (iii) |
| B C | B1 | |
| [1] | 1.1 | This graph o.e. with 10 directed arcs |
| Answer | Marks | Guidance |
|---|---|---|
| 4 | (b) | (iv) |
| C – A – B – C – A – D – C – D – B – C – B | M1 |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | Trail starts at C and ends at B (not reversed) and includes every |
Question 4:
4
4 | 9
11 9
4 | 9
4 | (a) | (i) | In complete graph K each vertex has
4
degree 3
In (a simply connected) Eulerian graph
(with 4 vertices) each vertex has even
degree so there is a contradiction | B1
B1
[2] | 2.4
2.4 | Complete (or K ) degree 3, allow odd
4
Diagrams are not sufficient explanation
Eulerian (or G) no odd (or all even), allow degree 2 o.e
Allow ‘some even’ or (at most) two odd (i.e. semi-Eulerian)
Diagrams are not sufficient explanation
Allow K has odd vertex degrees so not Eulerian for B1 B1
4
4 | (a) | (ii) | Number of arcs in graph G is 4
G is Eulerian so vertex degrees are even
G is connected so vertex degrees are not 0
G is simple so no vertex degree > 3
Hence each vertex of G has degree 2 | B1
B1
[2] | 2.2a
2.4 | 4
Explaining the significance of G being (Eulerian,) simple (and
connected) e.g. stating that each degree < 4, not just ‘no loops’
and hence each vertex has degree 2
Diagrams are not sufficient explanation
4 | (a) | (iii) | Each vertex of G is directly connected to
(only) 2 of the others
Use vertices that are not directly connected
to form the two sets. | B1
[1] | 1.1 | Showing that G is bipartite (no FT)
This could be shown in a diagram provided the two sets are
identified e.g. by drawing a ring round the vertices or from labels
(set 1 and set 2 o.e.)
If no indication of the sets, a diagram or with K stated
2,2
4 | (b) | (i) | The leading diagonal has all zero entries | B1
[1] | 2.2a | No arcs for each vertex to itself
Allow ‘A – A = 0 etc.’ o.e. (with B, C, D implied from etc.)
Diagrams are not sufficient explanation
4 | (b) | (ii) | The sum of the entries in the matrix is 10 | B1
[1] | 2.2a | 1+ 1+ … = 10 or 2 + 2 + 4 + 2 = 10, or similar
Allow 10 (without calculation)
4 | (b) | (iii) | A D
B C | B1
[1] | 1.1 | This graph o.e. with 10 directed arcs
For reference:
To
A B C D
A 0 1 0 1
From B 0 0 2 0
C 2 1 0 1
D 0 1 1 0
4 | (b) | (iv) | e.g.
C – A – B – C – A – D – C – D – B – C – B | M1
A1
[2] | 1.1
1.1 | Trail starts at C and ends at B (not reversed) and includes every
letter at least once
A valid trail (using each directed arc exactly once, no FT) that
passes through A, B and D (exactly) twice and passes through C
three times
2 A’s, 3 B’s, 4 C’s, 2 D’s4 Graph G is a simply connected Eulerian graph with 4 vertices.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Explain why graph G cannot be a complete graph.
\item Determine the number of arcs in graph G, explaining your reasoning.
\item Show that graph G is a bipartite graph.
Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H .
From
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{To}
\begin{tabular}{ l | l | l | l | l }
& A & B & C & D \\
\hline
A & 0 & 1 & 0 & 1 \\
\hline
B & 0 & 0 & 2 & 0 \\
\hline
C & 2 & 1 & 0 & 1 \\
\hline
D & 0 & 1 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\end{table}
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Write down a feature of the adjacency matrix that shows that H has no loops.
\item Find the number of $\operatorname { arcs }$ in H .
\item Draw a possible digraph H .
\item Show that digraph H is semi-Eulerian by writing down a suitable trail.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2023 Q4 [10]}}