| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2019 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Complete graph properties |
| Difficulty | Easy -1.2 This is a straightforward Further Maths Decision 1 question testing basic graph theory definitions and properties. Part (a) requires drawing K₅ (standard recall), part (b) tests the definition of semi-Eulerian and finding simple examples, and part (c) applies the tree property that sum of degrees equals 2(n-1). All parts are definitional or direct application with no problem-solving insight required, making it easier than average even for Further Maths. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02d Complete graphs: K_n and number of arcs7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| 1(a) | B1 | 1.2 |
| Answer | Marks | Guidance |
|---|---|---|
| (b)(i) | A semi-Eulerian graph contains exactly two nodes of odd order (and | |
| any number of nodes of even order) | B1 | 2.5 |
| (b)(ii) | e.g. (two semi- |
| Answer | Marks |
|---|---|
| number of edges) | B1 |
| B1 | 1.1b |
| Answer | Marks |
|---|---|
| (c) | 1+2+2+3+4 |
| Answer | Marks |
|---|---|
| tree on five nodes would contain only 4 arcs | B1 |
| B1dep | 2.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Question | Scheme | Marks |
| 1 | 3 | 4 |
| 82 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| 92.125 | 2 | |
| 124.125 | 2.5 | |
| 202.25 | 3 | 50.5625 |
| Question | Scheme | Marks |
Question 1:
--- 1(a) ---
1(a) | B1 | 1.2
(1)
(b)(i) | A semi-Eulerian graph contains exactly two nodes of odd order (and
any number of nodes of even order) | B1 | 2.5
(b)(ii) | e.g. (two semi-
Eulerian subgraphs of
K with a different
5
number of edges) | B1
B1 | 1.1b
1.1b
(3)
(c) | 1+2+2+3+4
e.g. The graph with five vertices has =6 arcs but a
2
tree on five nodes would contain only 4 arcs | B1
B1dep | 2.2a
2.4
(2)
(6 marks)
Notes
(a)
B1: CAO (give bod for position of nodes)
(b)(i)
B1: CAO (accept ‘there are exactly two odd nodes’ but must contain exact oe (e.g. ‘only two odd
nodes’ or ‘all but 2 nodes have an even order’ but not ‘the graph has two odd nodes’))
(b)(ii)
B1: One correct semi-Eulerian subgraph of K with five nodes
5
B1: Two correct semi-Eulerian subgraphs of K with five nodes – note that the graphs must have a
5
different number of edges
(c)
B1: Deducing that the graph has 6 arcs or a tree on five nodes has 4 arcs or the node of order 4 must
be connected to the other 4 nodes or an argument based on the sum of the orders of both the graph
and the tree (but must relate the orders to the number of arcs and not the number of nodes) or the
node with order 4 and one of the nodes of orders 2 or 3 would create a cycle or a tree must have two
nodes of order 1
B1dep: Complete argument – graph has 6 arcs and the tree would only have 4 arcs or the sum of the
orders is 12 compared to 8 for the tree or the node of order 4 must be connected to the other 4 nodes
therefore all the other vertices would have to have order 1 or the graph has 6 arcs and therefore with
5 vertices there would have to be cycles or the node of order 4 is connected to the other 4 nodes and
so together with the node of order 3 (or 2) a cycle would be formed or a tree must have at least two
nodes of order 1 as otherwise a cycle would be formed
Note: no marks in (c) for attempts based only on examples of graphs drawn with the vertex orders as
stated
Question | Scheme | Marks | AOs
1 | 3 | 4 | 0.5 | 0.25 | 0
82 | 1
1.5
92.125 | 2
124.125 | 2.5
202.25 | 3 | 50.5625
Question | Scheme | Marks | AOs\begin{enumerate}[label=(\alph*)]
\item Draw the graph $K_5$ [1]
\item \begin{enumerate}[label=(\roman*)]
\item In the context of graph theory explain what is meant by 'semi-Eulerian'.
\item Draw two semi-Eulerian subgraphs of $K_5$, each having five vertices but with a different number of edges. [3]
\end{enumerate}
\item Explain why a graph with exactly five vertices with vertex orders 1, 2, 2, 3 and 4 cannot be a tree. [2]
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2019 Q1 [6]}}