Question 2 - A-Level Maths

OCR Further Discrete 2021 November — Question 2 8 marks

Exam Board	OCR
Module	Further Discrete (Further Discrete)
Year	2021
Session	November
Marks	8
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Graph Theory Fundamentals
Type	Adjacency matrix interpretation
Difficulty	Standard +0.3 This question tests standard graph theory definitions and routine calculations. Part (a) requires applying the handshaking lemma to find degree constraints, part (b) lists degree sequences, and parts (c-d) involve reading an adjacency matrix and checking basic Eulerian/connectivity criteria. All steps are algorithmic with no novel problem-solving required, making it slightly easier than average.
Spec	7.02g Eulerian graphs: vertex degrees and traversability 7.02k Digraphs: directed graphs, indegree and outdegree 7.02q Adjacency matrix: and weighted matrix representation

2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.

1. Determine the minimum possible vertex degree.
2. Determine the maximum possible vertex degree.
Write down the two possible degree sequences (ordered lists of vertex degrees). The adjacency matrix for a digraph H is given below.
\multirow{7}{*}{From} \multirow{2}{*}{} To
J K L M N
J 0 1 1 0 0
K 1 0 1 0 0
L 1 0 0 0 1
M 0 0 2 1 1
N 0 1 0 1 0
Write down the indegree and the outdegree of each vertex of H .
1. Use the indegrees and outdegrees to determine whether graph H is Eulerian.
2. Use the adjacency matrix to determine whether graph H is simply connected.

Show mark scheme Show mark scheme source

Question 2:

Answer	Marks	Guidance
2	(a)	(i)
[1]	1.1	‘1’ and explaining why 0 is not possible
(ii)	4 because if there is a vertex of degree 5 then the other three vertices

must all be even and have degree sum 16 – (3+4+5) = 4, which is not

Answer	Marks	Guidance
possible	B1
[1]	1.1	‘4’ and explaining why 5 is not possible
2	(b)	1, 2, 2, 3, 4, 4
2, 2, 2, 3, 3, 4	M1

A1

Answer	Marks
[2]	1.1
1.2	Values in either list correct, given in any order

Both lists correct, in this form, each in increasing order

(allow decreasing order) and no others

Answer	Marks	Guidance
2	(c)	J K L M N

Indegree 2 2 4 2 2

Answer	Marks
Outdegree 2 2 2 4 2	M1

A1

Answer	Marks
[2]	1.1
1.2	Indegree = column total, outdegree = row total

Both rows correct, although rows may be interchanged

Completely correct

Answer	Marks	Guidance
2	(d)	(i)
outdegree for each vertex	B1
[1]	1.1	Not Eulerian, indegree  outdegree for L (or M)

Discussion of odd/even vertex degrees is wrong here,

need to use indegrees and outdegrees for a digraph

Saying ‘Eulerian since all even’ is also wrong

Answer	Marks	Guidance
(ii)	Connected but not simple, there are two arcs from M to L	B1

Alternative method

Not simple, there is a (directed) loop at M

[1]

Answer	Marks	Guidance
2	2	4
2	2	2
2	4	2

Question 2:
2 | (a) | (i) | 1 because the graph is connected | B1
[1] | 1.1 | ‘1’ and explaining why 0 is not possible
(ii) | 4 because if there is a vertex of degree 5 then the other three vertices
must all be even and have degree sum 16 – (3+4+5) = 4, which is not
possible | B1
[1] | 1.1 | ‘4’ and explaining why 5 is not possible
2 | (b) | 1, 2, 2, 3, 4, 4
2, 2, 2, 3, 3, 4 | M1
A1
[2] | 1.1
1.2 | Values in either list correct, given in any order
Both lists correct, in this form, each in increasing order
(allow decreasing order) and no others
2 | (c) | J K L M N
Indegree 2 2 4 2 2
Outdegree 2 2 2 4 2 | M1
A1
[2] | 1.1
1.2 | Indegree = column total, outdegree = row total
Both rows correct, although rows may be interchanged
Completely correct
2 | (d) | (i) | Not Eulerian, for a digraph to be Eulerian the indegree must equal the
outdegree for each vertex | B1
[1] | 1.1 | Not Eulerian, indegree  outdegree for L (or M)
Discussion of odd/even vertex degrees is wrong here,
need to use indegrees and outdegrees for a digraph
Saying ‘Eulerian since all even’ is also wrong
(ii) | Connected but not simple, there are two arcs from M to L | B1 | 1.1 | Not simple with a valid reason
Alternative method
Not simple, there is a (directed) loop at M
[1]
2 | 2 | 4 | 2 | 2
2 | 2 | 2 | 4 | 2
2 | 4 | 2

Show LaTeX source

2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Determine the minimum possible vertex degree.
\item Determine the maximum possible vertex degree.
\end{enumerate}\item Write down the two possible degree sequences (ordered lists of vertex degrees).

The adjacency matrix for a digraph H is given below.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
\multirow{7}{*}{From} & \multirow{2}{*}{} & \multicolumn{5}{|c|}{To} \\
\hline
 &  & J & K & L & M & N \\
\hline
 & J & 0 & 1 & 1 & 0 & 0 \\
\hline
 & K & 1 & 0 & 1 & 0 & 0 \\
\hline
 & L & 1 & 0 & 0 & 0 & 1 \\
\hline
 & M & 0 & 0 & 2 & 1 & 1 \\
\hline
 & N & 0 & 1 & 0 & 1 & 0 \\
\hline
\end{tabular}
\end{center}
\item Write down the indegree and the outdegree of each vertex of H .
\item \begin{enumerate}[label=(\roman*)]
\item Use the indegrees and outdegrees to determine whether graph H is Eulerian.
\item Use the adjacency matrix to determine whether graph H is simply connected.
\end{enumerate}\end{enumerate}

\hfill \mbox{\textit{OCR Further Discrete 2021 Q2 [8]}}

This paper (7 questions)

View full paper

Q1 8 Q2 8 Q3 8 Q4 13 Q5 12 Q6 11 Q7 15

\multirow{7}{*}{From}	\multirow{2}{*}{}	To
		J	K	L	M	N
	J	0	1	1	0	0
	K	1	0	1	0	0
	L	1	0	0	0	1
	M	0	0	2	1	1
	N	0	1	0	1	0