A2 June 2024 Q4

EdexcelCurrent spec8 marksGraphs & Networks

(a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 (1)

A tree, T, has exactly six nodes. The degrees of the six nodes of T are

\(1 \qquad 2 \qquad (4 - x) \qquad (2x - 5) \qquad (4x - 11) \qquad (3x - 5)\)

where \(x\) is an integer.

(b) Explain how you know that T cannot be Eulerian. (1)

(c)

(i) Determine the value of \(x\)

(ii) Hence state whether T is semi-Eulerian or not. You must justify your answer. (5)

Figure 2: graph G with six nodes of degrees 1, 2, 3, 3, 3 and 4 — 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. (1)

Diagram 1: six vertices with no arcs — Diagram 1

Mark scheme (a)

Scheme	Marks	AO
e.g. A graph cannot contain an odd number of odd vertices e.g. \(\dfrac{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	1.2
	(1)

Notes

(a) In a and b condone poor language such as number of odd degrees instead of number of odd nodes

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 (of the vertices) is 21 which is not even therefore not possible (but not just for obtaining 21 and saying ‘impossible’). The 21 must be linked either in words to the ‘sum of the degrees/order’ or explicitly showing 1+ 2 + 3 + 4 + 5 + 6 = 21 so just ’21 is not even’ scores B0
The sum of the degrees/order (of the vertices) is 21 which is odd therefore not possible (with equivalent justification of the 21 as in the previous bullet-point)
\(\dfrac{1+2+3+4+5+6}{2} = 10.5\) which is not an integer so therefore impossible. They do not have to explain that they are using the result that \(\sum \text{vertex degrees} = 2(\text{no of arcs})\) but they must explain why a value of 10.5 leads to the required graph not being possible. A value of 10.5 with no working (or explanation) scores B0

Mark scheme (b)

Scheme	Marks	AO
e.g. T has at least one node of degree one or one node with odd degree	B1	2.4
	(1)

Notes

(b) B1: CAO – correct reasoning that not all the vertices of T can have an even degree. Allow for this mark a general statement that no tree can be Eulerian as all trees contain at least two nodes of degree 1. Allow as a minimum statement that at least one of the nodes has a degree of 1 or at least one odd node (accept valency instead of degree or order)

Mark scheme (c)

Scheme	Marks	AO
6 nodes in T therefore the tree contains 5 arcs	B1	1.2
\(1 + 2 + (4 - x) + (2x - 5) + (4x - 11) + (3x - 5) = 2(5)\) \((8x - 14 = 10)\)	M1	3.1a
\(x = 3\)	A1	1.1b
Alternatively \(\begin{array}{llll} 4 - x \gt 0 & \Rightarrow\ x \lt 4 \qquad & 4 - x \geqslant 1 & \Rightarrow\ x \leqslant 3 \\ 2x - 5 \gt 0 & \Rightarrow\ x \gt 2.5 & 4x - 11 \geqslant 1 & \Rightarrow\ x \geqslant 3 \\ 2.5 \lt x \lt 4 & \Rightarrow\ x = 3 & & \phantom{\Rightarrow\ } x = 3 \end{array}\)
Therefore, the degrees of the nodes are 1, 2, 1, 1, 1 and 4	M1	2.1
T is not semi-Eulerian as there are more than two nodes of odd degree	A1	2.2a
	(5)

Notes

B1: correctly using the fact that the number of arcs in T is 5 (possibly implied by later working – e.g. forming an equation for the sum of nodes = 2 x 5) An answer of \(x = 3\) from correct working implies this mark.

Alternative approach either \(4 - x \gt 0 \;\Rightarrow\; x \lt 4\) or \(2x - 5 \gt 0 \;\Rightarrow\; x \gt 2.5\)
May use \(4x - 11 \geqslant 1 \;\Rightarrow\; x \geqslant 3\)

M1: Forming an equation involving the degree of the six nodes and 2(5).

Alternative approach both inequalities stated and combined to obtain range of values for \(x\)

A1: CAO (\(x = 3\)) – must come from correct working

M1: Calculating the degree of the remaining vertices using their value of \(x\). As a minimum we must see correct values for at least two more odd nodes. Must have an integer value for \(x\) (this can be implied by sight of 1, 2, 1, 1, 1, 4) Alternatively may clearly use \(x = 3\) is odd and deduce that there are at least three odd nodes

A1: CAO (not Semi-Eulerian) – with correct reasoning

four example graphs with six nodes of degrees 1, 2, 3, 3, 3 and 4 that are not isomorphic to G, two of them including multiple arcs or loops — Mark scheme (d)