A2 October 2021 Q1

EdexcelCurrent spec4 marksGraphs & Networks

Figure 1: bipartite graph with A, B, C, D, E on the left and U, V, W, X, Y on the right; edges AU, AV, AW, AX, BU, BV, BY, CU, CV, CW, CX, DW, DX, DY, EV, EX, EY — Figure 1

A Hamiltonian cycle for the graph in Figure 1 begins C, V, E, X, A, W, ….

(a) Complete the Hamiltonian cycle. (1)

(b) Hence use the planarity algorithm to determine whether the graph shown in Figure 1 is planar. You must make your working clear and justify your answer. (3)

the Hamiltonian cycle C, V, E, X, A, W, D, Y, B, U drawn as a polygon with the remaining arcs AU, AV, BV, CW, CX, DX and EY drawn inside — Mark scheme (b)

Scheme	Marks	AO
…, D, Y, B, U, C	B1	1.1b
	(1)

Scheme	Marks	AO
Or list of arcs: AU, AV, BV, CW, CX, DX, EY	M1	2.1
e.g., select (and label) AU (as I) and the arcs that intersect AU are BV, EY, CW and DX (so label them O so AU(I), AV, BV(O), CW(O), CX, DX(O), EY(O))	A1	1.1b
Edges BV and CW intersect and so the graph is not planar (oe)	A1	2.2a
	(3)
	(4 marks)

A2 October 2021 Q1

A2 October 2021 Q1

Notes

Notes