| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2018 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Moderate -0.8 This question tests basic graph theory definitions and simple counting principles. Parts (a) and (b) require minimal calculation (minimum arcs = 3 for a tree, maximum = 6 for complete graph K4) and straightforward application of Eulerian path criteria. Part (c) requires recognizing that 5 arcs forces a specific degree sequence (2,2,3,3), but this is still a direct application of definitions rather than novel problem-solving. Suitable for AS-level introduction to graph theory. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Minimum number of arcs is 3 | B1 | Cao |
| Maximum number of arcs is 6 | B1 | Cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A valid simple connected graph on 4 vertices with exactly 5 arcs (e.g. complete graph minus one edge) | B1 | Cao oe; vertices must be clear |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The graph has exactly two odd nodes | B1 | Explanation that graph has two odd nodes, consistent with their graph in (b)(i) |
| Therefore the graph is semi-Eulerian | DB1 | Exactly (or only) two odd nodes together with deduction that graph is semi-Eulerian; dependent on correct graph in (b)(i) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Sum of orders of vertices \(= 2(\text{number of arcs}) = 10\) | B1 | Implied if two or more lists of four numbers summing to 10 are seen |
| One possibility is that the orders are \(1, 3, 3, 3\) | M1 | States vertex orders could be \(1,3,3,3\) or that no vertex can have order greater than 3 |
| In a simply connected graph with four vertices, each vertex of order 3 must connect to the three other vertices, therefore it is not possible to have three vertices all with order 3 | A1 | Convincing argument that \(1,3,3,3\) is not possible |
| The second possibility is that the orders are \(2, 2, 3, 3\) | M1 | Considers possibility of orders being \(2,2,3,3\) |
| There is only one way to make a graph with vertices of orders \(2,2,3,3\) as the two vertices of order 2 cannot be connected to each other (no vertex can have order 0). There are no other possible graphs as maximum order of a vertex is 3 | A1 | Convincing argument only one way; mention that no vertex can have order greater than 3 required for full marks |
## Question 2:
### Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Minimum number of arcs is 3 | B1 | Cao |
| Maximum number of arcs is 6 | B1 | Cao |
### Part (b)(i)
| Answer | Mark | Guidance |
|--------|------|----------|
| A valid simple connected graph on 4 vertices with exactly 5 arcs (e.g. complete graph minus one edge) | B1 | Cao oe; vertices must be clear |
### Part (b)(ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| The graph has exactly two odd nodes | B1 | Explanation that graph has two odd nodes, consistent with their graph in (b)(i) |
| Therefore the graph is semi-Eulerian | DB1 | Exactly (or only) two odd nodes together with deduction that graph is semi-Eulerian; dependent on correct graph in (b)(i) |
### Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Sum of orders of vertices $= 2(\text{number of arcs}) = 10$ | B1 | Implied if two or more lists of four numbers summing to 10 are seen |
| One possibility is that the orders are $1, 3, 3, 3$ | M1 | States vertex orders could be $1,3,3,3$ or that no vertex can have order greater than 3 |
| In a simply connected graph with four vertices, each vertex of order 3 must connect to the three other vertices, therefore it is not possible to have three vertices all with order 3 | A1 | Convincing argument that $1,3,3,3$ is not possible |
| The second possibility is that the orders are $2, 2, 3, 3$ | M1 | Considers possibility of orders being $2,2,3,3$ |
| There is only one way to make a graph with vertices of orders $2,2,3,3$ as the two vertices of order 2 cannot be connected to each other (no vertex can have order 0). There are no other possible graphs as maximum order of a vertex is 3 | A1 | Convincing argument only one way; mention that no vertex can have order greater than 3 required for full marks |
---2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.
\begin{enumerate}[label=(\alph*)]
\item Given that a simply connected graph has exactly four vertices,
\begin{enumerate}[label=(\roman*)]
\item write down the minimum number of arcs it can have,
\item write down the maximum number of arcs it can have.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Draw a simply connected graph that has exactly four vertices and exactly five arcs.
\item State, with justification, whether your graph is Eulerian, semi-Eulerian or neither.
\end{enumerate}\item By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2018 Q2 [10]}}