AS June 2019 Q1

EdexcelAS paperCurrent spec6 marksGraphs & Networks

(a) Draw the graph \(\text{K}_5\) (1)

(b)

(i) In the context of graph theory explain what is meant by ‘semi-Eulerian’.

(ii) Draw two semi-Eulerian subgraphs of \(\text{K}_5\), each having five vertices but with a different number of edges. (3)

Scheme	Marks	AO
	B1	1.2
	(1)

six example semi-Eulerian subgraphs of K5, each on five vertices, with different numbers of edges — Mark scheme (b)

Scheme	Marks	AO
(i) A semi-Eulerian graph contains exactly two nodes of odd order (and any number of nodes of even order)	B1	2.5
(ii) e.g. (two semi-Eulerian subgraphs of \(\text{K}_5\) with a different number of edges)	B1 B1	1.1b 1.1b
	(3)

Mark scheme (c)

Scheme	Marks	AO
e.g. The graph with five vertices has \(\dfrac{1 + 2 + 2 + 3 + 4}{2} = 6\) arcs but a tree on five nodes would contain only 4 arcs	B1 B1dep	2.2a 2.4
	(2)
	(6 marks)

Notes

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