AS June 2018 Q2

EdexcelAS paperCurrent spec10 marksGraphs & Networks

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.

(a) Given that a simply connected graph has exactly four vertices,

(i) write down the minimum number of arcs it can have,

(ii) write down the maximum number of arcs it can have. (2)

(b)

(i) Draw a simply connected graph that has exactly four vertices and exactly five arcs.

(ii) State, with justification, whether your graph is Eulerian, semi-Eulerian or neither. (3)

(c) By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs. (5)

Scheme	Marks	AO
Minimum number of arcs is 3	B1	2.2a
Maximum number of arcs is 6	B1	2.2a
	(2)

a square on four vertices with one diagonal — Mark scheme (b)

Scheme	Marks	AO
(i) e.g.	B1	1.1b
(ii) The graph has exactly two odd nodes and so the graph is semi-Eulerian	B1 DB1	2.4 2.2a
	(3)

Mark scheme (c)

Scheme	Marks	AO
The sum of the orders of the vertices = 2(number of arcs) = 10	B1	1.2
One possibility is that the orders are 1, 3, 3 and 3	M1	2.1
In a simply connected graph with four vertices each of the vertices of order 3 must connect to the three other vertices therefore it is not possible to have three vertices all with order 3	A1	2.4
The second possibility is that the orders are 2, 2, 3 and 3	M1	2.1
There is only one way to make a graph with vertices of orders 2, 2, 3 and 3 as the two vertices of order 2 cannot be connected to each other (note that as the graph is connected no vertex can have order 0). There are no other possible graphs as the maximum order of a vertex is 3 (due to the condition that the graph must be simple)	A1	2.2a
	(5)
	(10 marks)

Notes

B1: 10 seen – this mark can be implied if two or more lists of four numbers which sum to 10 are seen

M1: States that the vertex orders could be 1, 3, 3, 3 or that no vertex can have an order greater than 3

A1: Convincing argument that 1, 3, 3, 3 is not possible

M1: Considers the possibility of the orders being 2, 2, 3, 3

A1: Convincing argument that there is only one way of making a graph with vertex orders of 2, 2, 3, 3 (e.g. mention of the fact that the two vertices of order 2 cannot be connected to each other)

For full marks in (c) – there must be some mention of the fact that there cannot be a vertex with order greater than 3 (withhold last A mark if this point is not considered)