| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Session | Specimen |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Finding variable values in degree sequences |
| Difficulty | Standard +0.3 This tests fundamental graph theory concepts (handshaking lemma, degree sequences, Eulerian paths) with straightforward application. Part (a) requires checking if sum of degrees is even, part (b) involves simple algebra and applying Eulerian criteria, and part (c) asks for a basic graph construction. All are standard textbook exercises requiring recall and routine application rather than problem-solving insight. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| e.g. a graph cannot contain an odd number of odd nodes; e.g. number of arcs \(= \frac{1+3+4+4+5}{2} = 8.5 \notin \mathbb{Z}\) | B1 | Explanation referring to need for an even number of odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \((2^{2x}-1)+(2^x)+(x+1)+(2^{x+1}-3)+(11-x) = 2(18)\) | M1 | Forming an equation involving the orders of the 5 odd nodes and \(2(18)\) |
| \(2^{2x}+3(2^x)-28=0 \Rightarrow x = \ldots\) | M1 | Simplifies to a quadratic in \(2^x\) and attempts to solve |
| \((2^x+7)(2^x-4)=0 \Rightarrow x=2\) | A1 | 2 cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| The order of the nodes are 9, 15, 3, 4, 5 | M1 | Construct an argument involving the order of the 5 nodes |
| Therefore the graph is neither Eulerian nor semi-Eulerian as there are more than two odd nodes | A1, A1 | A1: explanation considering number of odd nodes; A1: deduction that it is neither Eulerian nor semi-Eulerian |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| [Disconnected graph drawn] | M1 | Interprets mathematical language to construct a disconnected graph |
| [Correct graph] | A1 | Deduce a correct graph |
## Question 4(a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| e.g. a graph cannot contain an odd number of odd nodes; e.g. number of arcs $= \frac{1+3+4+4+5}{2} = 8.5 \notin \mathbb{Z}$ | B1 | Explanation referring to need for an even number of odd nodes |
## Question 4(b)(i):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $(2^{2x}-1)+(2^x)+(x+1)+(2^{x+1}-3)+(11-x) = 2(18)$ | M1 | Forming an equation involving the orders of the 5 odd nodes and $2(18)$ |
| $2^{2x}+3(2^x)-28=0 \Rightarrow x = \ldots$ | M1 | Simplifies to a quadratic in $2^x$ and attempts to solve |
| $(2^x+7)(2^x-4)=0 \Rightarrow x=2$ | A1 | 2 cao |
## Question 4(b)(ii):
| Answer/Working | Mark | Guidance |
|---|---|---|
| The order of the nodes are 9, 15, 3, 4, 5 | M1 | Construct an argument involving the order of the 5 nodes |
| Therefore the graph is neither Eulerian nor semi-Eulerian as there are more than two odd nodes | A1, A1 | A1: explanation considering number of odd nodes; A1: deduction that it is neither Eulerian nor semi-Eulerian |
## Question 4(c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| [Disconnected graph drawn] | M1 | Interprets mathematical language to construct a disconnected graph |
| [Correct graph] | A1 | Deduce a correct graph |
---4. (a) Explain why it is not possible to draw a graph with exactly 5 nodes with orders $1,3,4,4$ and 5
A connected graph has exactly 5 nodes and contains 18 arcs. The orders of the 5 nodes are $2 ^ { 2 x } - 1,2 ^ { x } , x + 1,2 ^ { x + 1 } - 3$ and $11 - x$.\\
(b) (i) Calculate X .\\
(ii) State whether the graph is Eulerian, semi-Eulerian or neither. You must justify your answer.\\
(c) Draw a graph which satisfies all of the following conditions:
\begin{itemize}
\item The graph has exactly 5 nodes.
\item The nodes have orders 2, 2, 4, 4 and 4
\item The graph is not Eulerian.
\end{itemize}
\hfill \mbox{\textit{Edexcel FD1 AS Q4 [9]}}