Standard +0.3 This is a multi-part question testing fundamental graph theory concepts (handshaking lemma, tree properties, Eulerian paths) with straightforward algebraic manipulation. Part (a) applies the handshaking lemma (sum of degrees must be even), part (b) recognizes trees have ≥2 odd-degree nodes, part (c) uses the tree property that sum of degrees = 2(n-1), and part (d) requires drawing a non-isomorphic graph with given degree sequence—all standard textbook exercises requiring recall and routine application rather than novel insight.
4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6
A tree, T , has exactly six nodes. The degrees of the six nodes of T are
1
2
\(( 4 - x )\)
\(( 2 x - 5 )\)
\(( 4 x - 11 )\)
\(( 3 x - 5 )\)
where \(x\) is an integer.
(b) Explain how you know that T cannot be Eulerian.
(c) (i) Determine the value of \(x\)
(ii) Hence state whether T is semi-Eulerian or not. You must justify your answer.
(5)
\includegraphics[max width=\textwidth, alt={}, center]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-07_588_579_977_744}
\section*{Figure 2}
Figure 2 shows a graph, \(G\), with six nodes with degrees \(1,2,3,3,3\) and 4
(d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees \(1,2,3,3,3\) and 4 that is not isomorphic to G .
A graph cannot contain an odd number of odd vertices. e.g. \(\frac{1+2+3+4+5+6}{2} = 10.5\) which is not an integer and so therefore not possible to have a graph with the given vertex orders
B1
CAO – common examples that score B1: Cannot have a graph with an odd number of odd vertices; Cannot have a graph with three odd vertices; The sum of the degrees/order is 21 which is not even therefore not possible; \(\frac{1+2+3+4+5+6}{2} = 10.5\) which is not an integer so therefore impossible
Part (b):
Answer
Marks
Guidance
Answer
Mark
Guidance
T has at least one node of degree one or one node with odd degree
B1
CAO – correct reasoning that not all vertices of T can have even degree. Allow a general statement that no tree can be Eulerian as all trees contain at least two nodes of degree 1. Accept valency instead of degree or order
Part (c):
Answer
Marks
Guidance
Answer
Mark
Guidance
6 nodes in T therefore the tree contains 5 arcs
B1
Correctly using the fact that number of arcs in T is 5. An answer of \(x=3\) from correct working implies this mark
Forming an equation involving the degree of the six nodes and \(2(5)\). Alternative: both inequalities stated and combined to obtain range of values for \(x\)
\(x=3\)
A1
CAO – must come from correct working
Therefore, the degrees of the nodes are 1, 2, 1, 1, 1 and 4
M1
Calculating the degree of the remaining vertices using their value of \(x\). Must see correct values for at least two more odd nodes. Must have an integer value for \(x\)
T is not semi-Eulerian as there are more than two nodes of odd degree
A1
CAO (not Semi-Eulerian) – with correct reasoning
Part (d):
Answer
Marks
Guidance
Answer
Mark
Guidance
[Graph diagram with degrees 1, 2, 3, 3, 3, 4]
B1
CAO – any graph that is not isomorphic to G – must contain exactly 8 arcs. If a simple, connected graph the vertex with degree 1 must connect to either the vertex of degree 2 or degree 4. Note this does not have to be a simple graph and may not be connected. (Degrees are 1, 2, 3, 3, 3, 4)
# Question 4:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| A graph cannot contain an odd number of odd vertices. e.g. $\frac{1+2+3+4+5+6}{2} = 10.5$ which is not an integer and so therefore not possible to have a graph with the given vertex orders | B1 | CAO – common examples that score B1: Cannot have a graph with an **odd number** of **odd vertices**; Cannot have a graph with **three odd vertices**; The **sum of the degrees/order** is **21** which is **not even** therefore **not possible**; $\frac{1+2+3+4+5+6}{2} = 10.5$ which is **not an integer** so therefore **impossible** |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| T has at least one node of degree one or one node with odd degree | B1 | CAO – correct reasoning that not all vertices of T can have even degree. Allow a general statement that no tree can be Eulerian as all trees contain at least two nodes of degree 1. Accept valency instead of degree or order |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| 6 nodes in T therefore the tree contains 5 arcs | B1 | Correctly using the fact that number of arcs in T is 5. An answer of $x=3$ from correct working implies this mark |
| $1+2+(4-x)+(2x-5)+(4x-11)+(3x-5)=2(5)$, $(8x-14=10)$ | M1 | Forming an equation involving the degree of the six nodes **and** $2(5)$. Alternative: both inequalities stated and combined to obtain range of values for $x$ |
| $x=3$ | A1 | CAO – must come from correct working |
| Therefore, the degrees of the nodes are 1, 2, 1, 1, 1 and 4 | M1 | Calculating the degree of the remaining vertices using their value of $x$. Must see correct values for at least two more odd nodes. Must have an integer value for $x$ |
| T is not semi-Eulerian as there are more than two nodes of odd degree | A1 | CAO (not Semi-Eulerian) – with correct reasoning |
## Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| [Graph diagram with degrees 1, 2, 3, 3, 3, 4] | B1 | CAO – any graph that is not isomorphic to G – must contain exactly 8 arcs. If a simple, connected graph the vertex with degree 1 must connect to either the vertex of degree 2 or degree 4. Note this does **not** have to be a simple graph and may **not** be connected. **(Degrees are 1, 2, 3, 3, 3, 4)** |
---
4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6
A tree, T , has exactly six nodes. The degrees of the six nodes of T are\\
1\\
2\\
$( 4 - x )$\\
$( 2 x - 5 )$\\
$( 4 x - 11 )$\\
$( 3 x - 5 )$\\
where $x$ is an integer.\\
(b) Explain how you know that T cannot be Eulerian.\\
(c) (i) Determine the value of $x$\\
(ii) Hence state whether T is semi-Eulerian or not. You must justify your answer.\\
(5)\\
\includegraphics[max width=\textwidth, alt={}, center]{7f7546eb-0c1a-40da-bdf0-31e0574a9867-07_588_579_977_744}
\section*{Figure 2}
Figure 2 shows a graph, $G$, with six nodes with degrees $1,2,3,3,3$ and 4\\
(d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees $1,2,3,3,3$ and 4 that is not isomorphic to G .\\
\hfill \mbox{\textit{Edexcel FD1 2024 Q4 [8]}}