D1-1 Algorithms and graph theory — revision question pack

4 specification points · notes, questions, answers and worked methods

Checked against Edexcel 9FM0 section D1-1. Review basis: the qualification registry sourced from the Pearson Edexcel Level 3 Advanced GCE in Further Mathematics (9FM0) specification; registry verification recorded 17 July 2026.

How this checking works

D1-1.1 · The general ideas of algorithms and the implementation of an algorithm given by a flow chart or text.

Explanation

An algorithm is a finite, unambiguous sequence of instructions that always terminates. In the exam it is given either as numbered text or as a flow chart, and the marks are for the trace, not for spotting the answer: build a table with one column per variable and one row per pass, and write every value the algorithm assigns.
The order of an algorithm measures its efficiency as a function of the size $n$ of the problem.
If an algorithm has order $n^2$ then multiplying the size by $k$ multiplies the run time by $k^2$ , so a time $T$ scales to $T\times k^2$ ; an order $n^3$ algorithm scales by $k^3$ .
Standard network algorithms such as Dijkstra's and Prim's have order $n^2$ , where $n$ counts the vertices.
To find the order from a count of operations, keep only the highest power of $n$ : $T(n)=3n^2+5n$ has order $n^2$ because the $5n$ term becomes negligible.

Worked example

An algorithm of order $n^2$ sorts $300$ items in $18$ seconds. Find the time it takes on $750$ items, and the largest number of items it can sort in $50$ seconds.

1.The size is multiplied by $750\div300=2.5$ , so the time is multiplied by $2.5^2=6.25$ .
2.The new time is $18\times6.25=112.5$ seconds.
3.For $50$ seconds the time factor is $50\div18=\frac{25}{9}$ , so the size factor is $\sqrt{25/9}=\frac53$ .
4.The largest size is $300\times\frac53=500$ items.

Answer: It takes $112.5$ seconds on $750$ items, and can sort at most $500$ items in $50$ seconds.

Common mistakes

Don't fall into the trap of scaling an order $n^2$ time by the size factor instead of by its square.
Don't fall into the trap of reading the loop condition after the update instead of before it, giving one row too many or too few.
Don't fall into the trap of quoting $3n^2+5n$ as the order rather than $n^2$ .

Exam tip

Draw the trace table before you start, with a column headed by every variable named in the algorithm; examiners award method marks for a correct partial table.

Tier 1 · Easy

1.
An algorithm is given in text form. Step 1: let $A=1$ and $B=1$ . Step 2: let $C=A+B$ . Step 3: let $A=B$ and then $B=C$ . Step 4: if $B\leqslant50$ go to Step 2, otherwise stop. Trace the algorithm and state the final values of $A$ and $B$ , and how many times Step 2 is carried out.
(4)
(Total for Question 1 is 4 marks)
2.
An algorithm has order $n^2$ . It takes $0.4$ seconds to run on a problem of size $200$ . Find the time it takes on a problem of size $500$ .
(2)
(Total for Question 2 is 2 marks)

Tier 2 · Standard

1.
A flow chart is described as follows. Box 1: input $N$ . Box 2: is $N=0$ ? If yes, output the count and stop. Box 3: replace $N$ by the integer part of $N\div2$ , add $1$ to the count, and return to Box 2. The count starts at $0$ . Trace the algorithm for $N=100$ , listing every value of $N$ , and state the output.
(4)
(Total for Question 1 is 4 marks)
2.
The number of operations an algorithm performs on a problem of size $n$ is $T(n)=3n^2+5n$ . Evaluate $T(10)$ and $T(40)$ , find $T(40)\div T(10)$ , and state the order of the algorithm, explaining why the ratio is not exactly $16$ .
(5)
(Total for Question 2 is 5 marks)
3.
An algorithm of order $n^3$ takes $2.5$ seconds on a problem of size $60$ . Find the time it takes on a problem of size $180$ , and state the order of Dijkstra's algorithm on a network with $n$ vertices.
(4)
(Total for Question 3 is 4 marks)

Tier 3 · Hard

1.
Euclid's algorithm is given as follows. Step 1: input $a$ and $b$ with $a>b$ . Step 2: let $q$ be the integer part of $a\div b$ and let $r=a-qb$ . Step 3: if $r=0$ output $b$ and stop; otherwise let $a=b$ , let $b=r$ and return to Step 2. Trace the algorithm for $a=1224$ and $b=546$ , recording $a$ , $b$ , $q$ and $r$ on each pass, and state the output.
(6)
(Total for Question 1 is 6 marks)
2.
An algorithm has order $n^2$ and takes $1.44$ seconds on a problem of size $120$ . Find the size of the largest problem it can complete in $9$ seconds, and the time it would take on a problem of size $420$ .
(5)
(Total for Question 2 is 5 marks)
3.
Two algorithms solve the same problem. Algorithm P has run time $0.002n^2$ seconds and algorithm Q has run time $0.00005n^3$ seconds, where $n$ is the size of the problem. Find the size at which the two run times are equal, state which algorithm is faster for $n=100$ , and justify the choice for large $n$ .
(6)
(Total for Question 3 is 6 marks)
4.
An algorithm compares every possible pair of items in a list of $n$ items exactly once. Write down the number of comparisons in terms of $n$ , evaluate it for $n=6$ and $n=20$ , and state the order of the algorithm with a reason.
(6)
(Total for Question 4 is 6 marks)
5.
A computer runs an order $n^2$ algorithm in $45$ seconds on a problem of size $300$ . Find the time on a problem of size $500$ , the largest size that can be completed in $80$ seconds, and the largest size after the computer is replaced by one that is $4$ times faster and is allowed the same $80$ seconds.
(7)
(Total for Question 5 is 7 marks)

D1-1.2 · Bin packing, bubble sort and quick sort.

Explanation

Bin packing places items of given sizes into bins of fixed capacity. The lower bound is $\left\lceil\dfrac{\text{total size}}{\text{bin capacity}}\right\rceil$ ; if a packing uses that many bins it is optimal.
First-fit takes the items in the order given and puts each one in the first bin it fits; first-fit decreasing sorts the items into descending order first; the full-bin method looks for combinations that fill bins exactly.
None of the three is guaranteed optimal.
In a bubble sort each pass compares adjacent items and swaps those in the wrong order; after pass $k$ the last $k$ items are in place, so pass $k$ makes $n-k$ comparisons, and the sort stops after a pass with no swaps.
In a quick sort the pivot is the middle item of the sublist, at position $\frac12(n+1)$ when $n$ is odd and $\frac12(n+2)$ when $n$ is even; every sublist that still has more than one item chooses a pivot on each pass, and chosen pivots are then fixed.

Worked example

Items of size $5, 8, 2, 7, 4, 6, 3$ are packed into bins of capacity $12$ . Find the lower bound and apply first-fit decreasing.

1.The total is $5+8+2+7+4+6+3=35$ , so the lower bound is $\lceil35\div12\rceil=\lceil2.9\dot{1}\dot{6}\rceil=3$ bins.
2.In descending order the items are $8, 7, 6, 5, 4, 3, 2$ .
3.Bin 1 takes $8$ then $4$ (total $12$ ); bin 2 takes $7$ then $5$ (total $12$ ); bin 3 takes $6$ , $3$ and $2$ (total $11$ ).
4.Three bins are used, which equals the lower bound.

Answer: The lower bound is $3$ bins, and first-fit decreasing achieves it with $\{8,4\}$ , $\{7,5\}$ and $\{6,3,2\}$ , so the packing is optimal.

Common mistakes

Don't fall into the trap of rounding the lower bound down instead of up.
Don't fall into the trap of restarting the search at the last bin used rather than at bin 1 in first-fit.
Don't fall into the trap of taking the pivot as the mean of the sublist, or as the middle item of the original list rather than of the current sublist.

Exam tip

Write the descending list out in full before starting first-fit decreasing; most lost marks are sorting slips, not packing slips.

Tier 1 · Easy

1.
Items of size $4, 7, 3, 6, 5, 2, 8, 5$ are to be packed into bins of capacity $10$ . Calculate a lower bound for the number of bins, then apply the first-fit algorithm to the list in the order given.
(5)
(Total for Question 1 is 5 marks)
2.
The list $27, 15, 34, 8, 22$ is to be sorted into ascending order using a bubble sort. Write down the list after the first complete pass, and state the number of comparisons made in that pass.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
Items of size $4, 7, 3, 6, 5, 2, 8, 5$ are to be packed into bins of capacity $10$ . Apply the first-fit decreasing algorithm and state, with a reason, whether your packing is optimal. You may use the lower bound of $4$ bins.
(5)
(Total for Question 1 is 5 marks)
2.
The list $31, 18, 45, 22, 9, 37, 26$ is to be sorted into descending order using a bubble sort. Write down the list after each of the first three passes.
(5)
(Total for Question 2 is 5 marks)
3.
The list $23, 41, 16, 35, 8, 29, 12, 47$ is to be sorted into ascending order using a quick sort. Write down the pivot chosen on the first pass and the result of the first two passes, showing the sublists clearly.
(5)
(Total for Question 3 is 5 marks)

Tier 3 · Hard

1.
Items of size $9, 12, 5, 14, 7, 3, 11, 8, 6$ are to be packed into bins of capacity $20$ . Calculate a lower bound, apply the first-fit algorithm in the order given, and state with a reason whether the result is optimal.
(6)
(Total for Question 1 is 6 marks)
2.
Items of size $9, 12, 5, 14, 7, 3, 11, 8, 6$ are to be packed into bins of capacity $20$ using the first-fit decreasing algorithm. Show the sorted list and the resulting packing, and explain why first-fit decreasing is still not guaranteed to be optimal in general.
(6)
(Total for Question 2 is 6 marks)
3.
The list $56, 21, 78, 34, 12, 65, 43$ is to be sorted into descending order using a quick sort. Carry out the algorithm in full, showing the pivots and the sublists after every pass, and state the number of passes needed.
(7)
(Total for Question 3 is 7 marks)
4.
The list $14, 9, 25, 6, 18, 11$ is to be sorted into ascending order using a quick sort. Carry out the algorithm in full, showing the pivot and the sublists after every pass, and state the number of passes needed.
(7)
(Total for Question 4 is 7 marks)
5.
Ten crates of weight $6, 11, 4, 9, 7, 13, 5, 8, 3, 10$ tonnes are to be loaded onto lorries with a capacity of $15$ tonnes each. Write down the list after the first two passes of a bubble sort into descending order, calculate a lower bound for the number of lorries, and apply the first-fit decreasing algorithm.
(8)
(Total for Question 5 is 8 marks)

D1-1.3 · Use of the order of the nodes to determine whether a graph is Eulerian, semi-Eulerian or neither.

Explanation

The order, or degree, of a node is the number of edges incident to it. The handshaking result says the degrees of a graph sum to $2E$ , where $E$ is the number of edges, so the number of odd nodes is always even.
A connected graph is Eulerian when every node has even order, and it then has a closed trail using every edge exactly once. It is semi-Eulerian when exactly two nodes have odd order, and any trail using every edge exactly once must start at one odd node and finish at the other.
With four or more odd nodes the graph is neither.
The complete graph $K_n$ has $n$ nodes, each of order $n-1$ , and $\frac{n(n-1)}{2}$ edges, so $K_n$ is Eulerian exactly when $n$ is odd.
Two graphs are isomorphic when they have the same number of vertices and the degrees of corresponding vertices match, so a difference in the sorted list of degrees is enough to prove that two graphs are not isomorphic.

Worked example

A connected graph has nodes of order $2, 2, 3, 3, 4, 4$ . Find the number of edges and classify the graph.

1.The degrees sum to $2+2+3+3+4+4=18$ .
2.The number of edges is $18\div2=9$ .
3.The odd nodes are the two of order $3$ .
4.Exactly two nodes are odd, so the graph is semi-Eulerian.

Answer: The graph has $9$ edges and is semi-Eulerian; a trail covering every edge once must start at one node of order $3$ and finish at the other.

Common mistakes

Don't fall into the trap of forgetting to halve the degree sum when counting edges.
Don't fall into the trap of calling a graph with four odd nodes semi-Eulerian.
Don't fall into the trap of claiming two graphs are isomorphic from a matching edge count alone, without checking the degrees.

Exam tip

List the degrees in order before answering; almost every part of these questions is settled by that list and the handshaking result.

Tier 1 · Easy

1.
A connected graph has nodes of order $2, 2, 4, 4, 4$ . Find the number of edges and state, with a reason, whether the graph is Eulerian, semi-Eulerian or neither.
(3)
(Total for Question 1 is 3 marks)
2.
A connected graph has vertices $A$ , $B$ , $C$ , $D$ , $E$ and edges $AB$ , $AC$ , $BC$ , $BD$ , $CE$ , $DE$ . Write down the order of each vertex and classify the graph.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
A connected graph has vertices $A$ , $B$ , $C$ , $D$ , $E$ , $F$ and edges $AB$ , $AC$ , $AE$ , $BC$ , $BD$ , $CD$ , $DF$ , $EF$ . Write down the order of each vertex, classify the graph, and state the smallest number of edges that would have to be added to make it Eulerian.
(5)
(Total for Question 1 is 5 marks)
2.
Write down the number of edges of the complete graph $K_7$ and the order of each of its vertices. State, with a reason, whether $K_7$ is Eulerian, and find the smallest $n$ greater than $7$ for which $K_n$ is Eulerian.
(5)
(Total for Question 2 is 5 marks)
3.
A connected graph has $13$ edges and $8$ vertices. Seven of the vertices have orders $3, 3, 3, 4, 4, 4, 4$ . Find the order of the eighth vertex and classify the graph.
(4)
(Total for Question 3 is 4 marks)

Tier 3 · Hard

1.
A connected graph has vertices $A$ , $B$ , $C$ , $D$ , $E$ and edges $AB$ , $AC$ , $AD$ , $BC$ , $BE$ , $CD$ , $CE$ , $DE$ . Write down the order of each vertex, classify the graph, and state the number of edges that a trail starting and finishing at $A$ would have to repeat if it must cover every edge.
(6)
(Total for Question 1 is 6 marks)
2.
Graph $G$ has $6$ vertices with orders $2, 2, 3, 3, 4, 4$ and graph $H$ has $6$ vertices with orders $2, 3, 3, 3, 3, 4$ . Show that $G$ and $H$ have the same number of edges, explain why they cannot be isomorphic, and classify each graph.
(6)
(Total for Question 2 is 6 marks)
3.
A connected graph has $n$ vertices, every one of order $4$ , and $18$ edges. Find $n$ , classify the graph, and determine how many edges a graph with $n$ vertices all of order $4$ would have in general.
(5)
(Total for Question 3 is 5 marks)
4.
Explain why a graph cannot have exactly three vertices of odd order, and hence write down the possible numbers of odd vertices in a graph with $7$ vertices. Determine whether a connected graph with $7$ vertices of orders $1, 2, 2, 3, 3, 4, 5$ exists.
(6)
(Total for Question 4 is 6 marks)
5.
A connected graph $G$ has $6$ vertices $A$ to $F$ and is semi-Eulerian, with a trail covering every edge exactly once running from $A$ to $F$ . The orders of $B$ , $C$ , $D$ and $E$ are $4$ , $2$ , $4$ and $2$ , and $G$ has $9$ edges. Find the orders of $A$ and $F$ , and state how many edges must be added so that a closed trail covering every edge exactly once exists, naming a suitable edge.
(6)
(Total for Question 5 is 6 marks)

D1-1.4 · The planarity algorithm for planar graphs.

Explanation

A graph is planar when it can be drawn so that edges meet only at vertices. The planarity algorithm applies to a graph that contains a Hamiltonian cycle, a cycle passing through every vertex exactly once.
Redraw that cycle as a circle with the vertices in cycle order, then every remaining edge is a chord that must be drawn either inside or outside the circle. Two chords conflict when they cross, which happens exactly when the endpoints of one separate the endpoints of the other around the cycle; chords sharing a vertex never conflict.
Build the conflict list, then try to label each chord I for inside or O for outside so that conflicting chords get different labels.
If a consistent labelling exists the graph is planar and the labelling is a recipe for a plane drawing.
If following the conflicts forces a chord to take both labels, no plane drawing exists and the graph is not planar; $K_5$ and $K_{3,3}$ both fail in exactly this way.

Worked example

A graph has the Hamiltonian cycle $ABCDEA$ and the additional edges $AC$ , $AD$ and $BD$ . Use the planarity algorithm to decide whether it is planar.

1.Draw $A, B, C, D, E$ around a circle in that order; the chords are $AC$ , $AD$ and $BD$ .
2. $AC$ and $AD$ share $A$ , and $AD$ and $BD$ share $D$ , so neither pair conflicts.
3. $AC$ separates $B$ from $D$ and $E$ , and the chord $BD$ has one endpoint on each side, so $AC$ and $BD$ conflict.
4.Label $AC$ as I; then $BD$ must be O; $AD$ conflicts with nothing so it may be I.

Answer: A consistent labelling exists, with $AC$ and $AD$ inside and $BD$ outside, so the graph is planar.

Common mistakes

Don't fall into the trap of treating two chords that share a vertex as conflicting.
Don't fall into the trap of stopping at one crossing drawing and concluding the graph is not planar, instead of testing every labelling through the conflict list.
Don't fall into the trap of applying the algorithm without first identifying a Hamiltonian cycle.

Exam tip

Write the cycle order along the top of your working and read each chord as the set of vertices it separates; the conflicts then fall out mechanically.

Tier 1 · Easy

1.
Explain what is meant by a Hamiltonian cycle, and write down a Hamiltonian cycle for the complete graph $K_4$ with vertices $A$ , $B$ , $C$ , $D$ .
(3)
(Total for Question 1 is 3 marks)
2.
A graph has the Hamiltonian cycle $ABCDEFA$ and the two additional edges $AC$ and $DF$ . Decide whether these two chords conflict, and hence state whether the graph is planar.
(3)
(Total for Question 2 is 3 marks)

Tier 2 · Standard

1.
A graph has the Hamiltonian cycle $ABCDEFA$ and the additional edges $AC$ , $BD$ , $CE$ and $DF$ . Use the planarity algorithm to determine whether the graph is planar, listing the conflicts and giving a labelling.
(6)
(Total for Question 1 is 6 marks)
2.
The complete bipartite graph $K_{3,3}$ has vertices $A$ , $B$ , $C$ joined to each of $D$ , $E$ , $F$ . Verify that $ADBECFA$ is a Hamiltonian cycle, list the remaining edges, and determine the conflicts between them.
(6)
(Total for Question 2 is 6 marks)
3.
A graph has the Hamiltonian cycle $ABCDEFA$ and the additional edges $AD$ , $BE$ and $CF$ . Determine the conflicts and state, with a reason, whether the graph is planar.
(5)
(Total for Question 3 is 5 marks)

Tier 3 · Hard

1.
Use the planarity algorithm on the complete graph $K_5$ with vertices $A$ , $B$ , $C$ , $D$ , $E$ and Hamiltonian cycle $ABCDEA$ to show that $K_5$ is not planar. List the chords, the complete set of conflicts, and explain precisely why no labelling succeeds.
(8)
(Total for Question 1 is 8 marks)
2.
A graph has the Hamiltonian cycle $ABCDEFA$ and the additional edges $AC$ , $AE$ , $BF$ and $CE$ . Apply the planarity algorithm, giving the conflicts and a labelling, and state whether the graph is planar.
(7)
(Total for Question 2 is 7 marks)
3.
Explain why the planarity algorithm requires a Hamiltonian cycle, and describe what the algorithm can and cannot conclude about a graph in which no Hamiltonian cycle can be found.
(6)
(Total for Question 3 is 6 marks)
4.
A graph has the Hamiltonian cycle $ABCDEFA$ and the additional edges $AC$ , $AD$ , $BD$ , $BF$ and $CF$ . Apply the planarity algorithm and determine whether the graph is planar, showing the conflicts you use.
(8)
(Total for Question 4 is 8 marks)
5.
A graph has $7$ vertices, the Hamiltonian cycle $ABCDEFGA$ and the additional edges $AC$ , $AD$ , $AE$ , $BF$ and $CF$ . Apply the planarity algorithm, listing every conflict, and give a labelling or explain why none exists.
(8)
(Total for Question 5 is 8 marks)

Answer key

Answers begin on a new printed page so the question pack can be completed without the solutions alongside it.

D1-1.1 · The general ideas of algorithms and the implementation of an algorithm given by a flow chart or text.

Tier 1 · Easy

Mark scheme for D1-1.1 Tier 1 · Easy
Question	Scheme	Marks
1	The values of $B$ produced are $2, 3, 5, 8, 13, 21, 34, 55$ Final $A=34$ Final $B=55$ Step 2 is carried out $8$ times	4
(4 marks)		4
Notes
Each pass replaces the pair $(A,B)$ by $(B,A+B)$ , giving $(1,2)$ , $(2,3)$ , $(3,5)$ , $(5,8)$ , $(8,13)$ , $(13,21)$ , $(21,34)$ and $(34,55)$ . The test at Step 4 first fails when $B=55>50$ , after $8$ passes, so the algorithm stops with $A=34$ and $B=55$ .
2	Size factor $500\div200=2.5$ Time factor $2.5^2=6.25$ Time $=0.4\times6.25=2.5$ seconds	2
(2 marks)		2
Notes
For an order $n^2$ algorithm the run time is proportional to $n^2$ . The size is multiplied by $2.5$ , so the time is multiplied by $2.5^2=6.25$ , giving $0.4\times6.25=2.5$ seconds.

Tier 2 · Standard

Mark scheme for D1-1.1 Tier 2 · Standard
Question	Scheme	Marks
1	$N$ takes the values $100, 50, 25, 12, 6, 3, 1, 0$ The count increases by $1$ each time Box 3 is used Output $=7$	4
(4 marks)		4
Notes
Halving and taking the integer part gives $100\to50\to25\to12\to6\to3\to1\to0$ , where $25\div2=12.5$ has integer part $12$ and $3\div2=1.5$ has integer part $1$ . Box 3 is used $7$ times before the test at Box 2 succeeds, so the output is $7$ .
2	$T(10)=300+50=350$ $T(40)=4800+200=5000$ $T(40)\div T(10)=\dfrac{5000}{350}=\dfrac{100}{7}=14.3$ to $3$ significant figures The order is $n^2$ The ratio falls short of $16$ because the linear term $5n$ is still a noticeable share of $T(10)$	5
(5 marks)		5
Notes
Substituting gives $T(10)=3(100)+5(10)=350$ and $T(40)=3(1600)+5(40)=5000$ , so the ratio is $5000/350=100/7\approx14.3$ . The dominant term for large $n$ is $3n^2$ , so the order is $n^2$ and the ideal ratio would be $4^2=16$ . At $n=10$ the term $5n=50$ is about $14\%$ of $T(10)$ but at $n=40$ the term $5n=200$ is only $4\%$ of $T(40)$ , so the measured ratio is below $16$ .
3	Size factor $180\div60=3$ Time factor $3^3=27$ Time $=2.5\times27=67.5$ seconds Dijkstra's algorithm has order $n^2$	4
(4 marks)		4
Notes
An order $n^3$ run time is proportional to $n^3$ , so tripling the size multiplies the time by $3^3=27$ , giving $2.5\times27=67.5$ seconds. Dijkstra's algorithm assigns a permanent label to each of the $n$ vertices and updates at most $n$ working values each time, so it is a standard order $n^2$ network algorithm.

Tier 3 · Hard

Mark scheme for D1-1.1 Tier 3 · Hard
Question	Scheme	Marks
1	Pass 1: $a=1224$ , $b=546$ , $q=2$ , $r=132$ Pass 2: $a=546$ , $b=132$ , $q=4$ , $r=18$ Pass 3: $a=132$ , $b=18$ , $q=7$ , $r=6$ Pass 4: $a=18$ , $b=6$ , $q=3$ , $r=0$ Output $=6$ The output is the greatest common divisor of $1224$ and $546$	6
(6 marks)		6
Notes
Each pass computes $r=a-qb$ and then shifts the pair. Since $1224=2(546)+132$ , $546=4(132)+18$ , $132=7(18)+6$ and $18=3(6)+0$ , the remainder first reaches $0$ on the fourth pass with $b=6$ , so the algorithm outputs $6$ .
2	Time factor $9\div1.44=6.25$ Size factor $\sqrt{6.25}=2.5$ Largest size $=120\times2.5=300$ Size factor $420\div120=3.5$ , so time factor $3.5^2=12.25$ Time $=1.44\times12.25=17.64$ seconds	5
(5 marks)		5
Notes
Run time is proportional to $n^2$ , so $t=cn^2$ with $c=1.44\div120^2=10^{-4}$ . For $t=9$ , $n^2=9\div10^{-4}=90000$ and $n=300$ . For $n=420$ , $t=10^{-4}\times420^2=10^{-4}\times176400=17.64$ seconds.
3	$0.002n^2=0.00005n^3$ $n=0.002\div0.00005=40$ At $n=100$ : P takes $20$ seconds and Q takes $50$ seconds Algorithm P is faster at $n=100$ P is faster for every $n>40$ P has the lower order, $n^2$ against $n^3$ , so it wins for all large $n$	6
(6 marks)		6
Notes
Setting the times equal gives $0.002n^2=0.00005n^3$ , and dividing by $n^2$ (with $n>0$ ) gives $n=0.002/0.00005=40$ . At $n=100$ , algorithm P takes $0.002\times10000=20$ seconds while algorithm Q takes $0.00005\times10^6=50$ seconds, so P is faster. Since the ratio of Q's time to P's time is $0.025n$ , which exceeds $1$ whenever $n>40$ , algorithm P is faster for every larger problem, as its lower order guarantees.
4	Number of comparisons $=\dfrac{n(n-1)}{2}$ For $n=6$ : $\dfrac{6\times5}{2}=15$ For $n=20$ : $\dfrac{20\times19}{2}=190$ $\dfrac{n(n-1)}{2}=\dfrac12n^2-\dfrac12n$ The order is $n^2$ The highest power of $n$ present is $n^2$ , and the $-\frac12n$ term is negligible for large $n$	6
(6 marks)		6
Notes
Choosing an unordered pair from $n$ items can be done in $\binom{n}{2}=\frac{n(n-1)}{2}$ ways, so that is the comparison count: $15$ when $n=6$ and $190$ when $n=20$ . Expanding gives $\frac12n^2-\frac12n$ , whose dominant term is $\frac12n^2$ , so the algorithm has order $n^2$ .
5	Size factor $500\div300=\dfrac53$ , so time factor $\left(\dfrac53\right)^2=\dfrac{25}{9}$ Time $=45\times\dfrac{25}{9}=125$ seconds For $80$ seconds the time factor is $\dfrac{80}{45}=\dfrac{16}{9}$ Size factor $=\sqrt{16/9}=\dfrac43$ Largest size $=300\times\dfrac43=400$ A computer $4$ times faster multiplies the allowed time factor by $4$ , so the size factor gains $\sqrt4=2$ Largest size $=400\times2=800$	7
(7 marks)		7
Notes
Run time satisfies $t=cn^2$ with $c=45\div300^2=5\times10^{-4}$ . For $n=500$ , $t=5\times10^{-4}\times250000=125$ seconds. For $t=80$ , $n^2=80\div(5\times10^{-4})=160000$ , so $n=400$ . Making the machine $4$ times faster replaces $c$ by $c/4$ , so $n^2=80\div(1.25\times10^{-4})=640000$ and $n=800$ ; equivalently, a factor $4$ in speed buys only a factor $\sqrt4=2$ in size for a quadratic algorithm.

D1-1.2 · Bin packing, bubble sort and quick sort.

Tier 1 · Easy

Mark scheme for D1-1.2 Tier 1 · Easy
Question	Scheme	Marks
1	Total size $=40$ Lower bound $=\left\lceil\dfrac{40}{10}\right\rceil=4$ bins Bin 1: $4, 3, 2$ Bin 2: $7$ Bin 3: $6$ Bin 4: $5, 5$ Bin 5: $8$ First-fit uses $5$ bins	5
(5 marks)		5
Notes
The items total $40$ , so at least $40\div10=4$ bins are needed. Working along the list, $4$ opens bin 1; $7$ will not fit with it so opens bin 2; $3$ fits in bin 1; $6$ opens bin 3; $5$ opens bin 4; $2$ fits in bin 1, filling it to $9$ ; $8$ fits nowhere so opens bin 5; the final $5$ fits in bin 4, filling it to $10$ . Five bins are used.
2	After the first pass: $15, 27, 8, 22, 34$ $4$ comparisons	3
(3 marks)		3
Notes
Comparing adjacent pairs left to right: $27$ and $15$ swap to give $15, 27, 34, 8, 22$ ; $27$ and $34$ do not swap; $34$ and $8$ swap to give $15, 27, 8, 34, 22$ ; $34$ and $22$ swap to give $15, 27, 8, 22, 34$ . A list of $5$ items needs $4$ comparisons in the first pass, and the largest item $34$ has reached the end.

Tier 2 · Standard

Mark scheme for D1-1.2 Tier 2 · Standard
Question	Scheme	Marks
1	Descending order: $8, 7, 6, 5, 5, 4, 3, 2$ Bin 1: $8, 2$ Bin 2: $7, 3$ Bin 3: $6, 4$ Bin 4: $5, 5$ First-fit decreasing uses $4$ bins This equals the lower bound, so the packing is optimal	5
(5 marks)		5
Notes
Sorting into descending order gives $8, 7, 6, 5, 5, 4, 3, 2$ . Then $8$ opens bin 1, $7$ opens bin 2, $6$ opens bin 3, the first $5$ opens bin 4 and the second $5$ joins it to make $10$ ; $4$ fits in bin 3 making $10$ ; $3$ fits in bin 2 making $10$ ; $2$ fits in bin 1 making $10$ . All four bins are exactly full, and since the lower bound is $4$ no packing can do better.
2	After pass 1: $31, 45, 22, 18, 37, 26, 9$ After pass 2: $45, 31, 22, 37, 26, 18, 9$ After pass 3: $45, 31, 37, 26, 22, 18, 9$	5
(5 marks)		5
Notes
For a descending sort a pair is swapped when the left item is smaller. Pass 1 swaps $18$ with $45$ , then $18$ with $22$ , then $9$ with $37$ and $9$ with $26$ , sending $9$ to the end and giving $31, 45, 22, 18, 37, 26, 9$ . Pass 2 works on the first six items and swaps $31$ with $45$ , then $18$ with $37$ and $18$ with $26$ , giving $45, 31, 22, 37, 26, 18, 9$ . Pass 3 works on the first five and swaps $22$ with $37$ and then $22$ with $26$ , giving $45, 31, 37, 26, 22, 18, 9$ .
3	The list has $8$ items, so the pivot is item $\tfrac12(8+2)=5$ , namely $8$ After pass 1: $[8]$ , $[23, 41, 16, 35, 29, 12, 47]$ The second sublist has $7$ items, so its pivot is item $\tfrac12(7+1)=4$ , namely $35$ After pass 2: $[8]$ , $[23, 16, 29, 12]$ , $[35]$ , $[41, 47]$	5
(5 marks)		5
Notes
With $n=8$ the middle item is in position $\frac12(n+2)=5$ , which holds $8$ . Nothing is smaller than $8$ , so pass 1 gives the fixed pivot $8$ followed by the sublist $23, 41, 16, 35, 29, 12, 47$ in its original relative order. That sublist has $n=7$ , so its pivot is in position $\frac12(7+1)=4$ , which holds $35$ . Items smaller than $35$ are $23, 16, 29, 12$ and items larger are $41, 47$ , so pass 2 gives $[8]$ , $[23, 16, 29, 12]$ , $[35]$ , $[41, 47]$ .

Tier 3 · Hard

Mark scheme for D1-1.2 Tier 3 · Hard
Question	Scheme	Marks
1	Total size $=75$ Lower bound $=\left\lceil\dfrac{75}{20}\right\rceil=\lceil3.75\rceil=4$ bins Bin 1: $9, 5, 3$ (total $17$ ) Bin 2: $12, 7$ (total $19$ ) Bin 3: $14, 6$ (total $20$ ) Bin 4: $11, 8$ (total $19$ ) First-fit uses $4$ bins, which equals the lower bound, so the packing is optimal	6
(6 marks)		6
Notes
The items total $75$ , so at least $\lceil75/20\rceil=4$ bins are needed. First-fit gives: $9$ opens bin 1; $12$ opens bin 2; $5$ joins bin 1 ( $14$ ); $14$ opens bin 3; $7$ joins bin 2 ( $19$ ); $3$ joins bin 1 ( $17$ ); $11$ opens bin 4; $8$ joins bin 4 ( $19$ ); $6$ joins bin 3 ( $20$ ). Four bins are used, matching the lower bound, so no packing uses fewer.
2	Descending order: $14, 12, 11, 9, 8, 7, 6, 5, 3$ Bin 1: $14, 6$ (total $20$ ) Bin 2: $12, 8$ (total $20$ ) Bin 3: $11, 9$ (total $20$ ) Bin 4: $7, 5, 3$ (total $15$ ) First-fit decreasing uses $4$ bins It is a heuristic: it makes a locally best choice for each item in turn and never reconsiders an earlier placement, so on other data it can use more bins than the optimum	6
(6 marks)		6
Notes
Sorting gives $14, 12, 11, 9, 8, 7, 6, 5, 3$ . Then $14$ opens bin 1, $12$ opens bin 2, $11$ opens bin 3, $9$ joins bin 3 ( $20$ ), $8$ joins bin 2 ( $20$ ), $7$ opens bin 4, $6$ joins bin 1 ( $20$ ), $5$ joins bin 4 ( $12$ ) and $3$ joins bin 4 ( $15$ ). Four bins are used. First-fit decreasing places each item in the first bin with room and never moves it again, so it cannot recover from an early placement that blocks a later exact fit; that is why an examiner asks for the lower bound before accepting a packing as optimal.
3	Pass 1 pivot: item $\tfrac12(7+1)=4$ , namely $34$ ; result $[56, 78, 65, 43]$ , $[34]$ , $[21, 12]$ Pass 2 pivots: $65$ from the first sublist and $12$ from the last; result $[78]$ , $[65]$ , $[56, 43]$ , $[34]$ , $[21]$ , $[12]$ Pass 3 pivot: $43$ ; result $[78]$ , $[65]$ , $[56]$ , $[43]$ , $[34]$ , $[21]$ , $[12]$ Sorted list: $78, 65, 56, 43, 34, 21, 12$ $3$ passes are needed	7
(7 marks)		7
Notes
For a descending sort, items larger than the pivot are written before it. With $n=7$ the first pivot is in position $4$ , namely $34$ ; the larger items $56, 78, 65, 43$ go before it and the smaller items $21, 12$ after it. On pass 2 the sublist $56, 78, 65, 43$ has $n=4$ and pivot in position $\frac12(4+2)=3$ , namely $65$ , giving $[78]$ , $[65]$ , $[56, 43]$ ; the sublist $21, 12$ has $n=2$ and pivot in position $2$ , namely $12$ , giving $[21]$ , $[12]$ . On pass 3 the only sublist left is $56, 43$ , whose pivot is $43$ , giving $[56]$ , $[43]$ . Every item is now a chosen pivot, so the sort is complete after $3$ passes.
4	Pass 1 pivot: item $\tfrac12(6+2)=4$ , namely $6$ ; result $[6]$ , $[14, 9, 25, 18, 11]$ Pass 2 pivot: $25$ ; result $[6]$ , $[14, 9, 18, 11]$ , $[25]$ Pass 3 pivot: $18$ ; result $[6]$ , $[14, 9, 11]$ , $[18]$ , $[25]$ Pass 4 pivot: $9$ ; result $[6]$ , $[9]$ , $[14, 11]$ , $[18]$ , $[25]$ Pass 5 pivot: $11$ ; result $[6]$ , $[9]$ , $[11]$ , $[14]$ , $[18]$ , $[25]$ $5$ passes are needed	7
(7 marks)		7
Notes
With $n=6$ the first pivot is in position $\frac12(6+2)=4$ , namely $6$ ; nothing is smaller, so the pass gives $[6]$ then $14, 9, 25, 18, 11$ . That sublist has $n=5$ and pivot in position $3$ , namely $25$ , and nothing is larger, giving $[14, 9, 18, 11]$ , $[25]$ . Next $n=4$ and the pivot is in position $3$ , namely $18$ , giving $[14, 9, 11]$ , $[18]$ . Then $n=3$ with pivot in position $2$ , namely $9$ , giving $[9]$ , $[14, 11]$ . Finally $n=2$ with pivot in position $2$ , namely $11$ , giving $[11]$ , $[14]$ . Five passes are needed because each pass fixes only the pivots of the sublists that are still active.
5	After pass 1: $11, 6, 9, 7, 13, 5, 8, 4, 10, 3$ After pass 2: $11, 9, 7, 13, 6, 8, 5, 10, 4, 3$ Total weight $=76$ tonnes Lower bound $=\left\lceil\dfrac{76}{15}\right\rceil=\lceil5.0\dot{6}\rceil=6$ lorries Descending order: $13, 11, 10, 9, 8, 7, 6, 5, 4, 3$ Lorry 1: $13$ ; lorry 2: $11, 4$ ; lorry 3: $10, 5$ ; lorry 4: $9, 6$ ; lorry 5: $8, 7$ ; lorry 6: $3$ First-fit decreasing uses $6$ lorries, which equals the lower bound, so it is optimal	8
(8 marks)		8
Notes
In a descending bubble sort a pair is swapped when the left value is the smaller. Pass 1 makes nine comparisons and swaps $6$ with $11$ , then carries $4$ rightwards past $9$ , $7$ , $13$ , $5$ and $8$ , and finally swaps $3$ with $10$ , giving $11, 6, 9, 7, 13, 5, 8, 4, 10, 3$ . Pass 2 works on the first nine entries, makes eight comparisons and carries $6$ past $9$ , $7$ and $13$ , then $5$ past $8$ and $4$ past $10$ , giving $11, 9, 7, 13, 6, 8, 5, 10, 4, 3$ . The crates total $6+11+4+9+7+13+5+8+3+10=76$ tonnes, so at least $\lceil76/15\rceil=6$ lorries are needed. Applying first-fit to $13, 11, 10, 9, 8, 7, 6, 5, 4, 3$ : $13$ opens lorry 1; $11$ opens lorry 2; $10$ opens lorry 3; $9$ opens lorry 4; $8$ opens lorry 5; $7$ joins lorry 5 ( $15$ ); $6$ joins lorry 4 ( $15$ ); $5$ joins lorry 3 ( $15$ ); $4$ joins lorry 2 ( $15$ ); $3$ fits nowhere and opens lorry 6. Six lorries are used, matching the lower bound.

D1-1.3 · Use of the order of the nodes to determine whether a graph is Eulerian, semi-Eulerian or neither.

Tier 1 · Easy

Mark scheme for D1-1.3 Tier 1 · Easy
Question	Scheme	Marks
1	Sum of orders $=16$ Number of edges $=16\div2=8$ Every node has even order, so the graph is Eulerian	3
(3 marks)		3
Notes
The orders sum to $2+2+4+4+4=16$ , and each edge contributes $2$ to that sum, so there are $8$ edges. There are no odd nodes, so a connected graph of this type is Eulerian and has a closed trail using every edge exactly once.
2	Orders: $A$ is $2$ , $B$ is $3$ , $C$ is $3$ , $D$ is $2$ , $E$ is $2$ Exactly two vertices, $B$ and $C$ , have odd order The graph is semi-Eulerian	3
(3 marks)		3
Notes
Counting the edges at each vertex gives $A$ in $AB, AC$ so order $2$ ; $B$ in $AB, BC, BD$ so order $3$ ; $C$ in $AC, BC, CE$ so order $3$ ; $D$ in $BD, DE$ so order $2$ ; and $E$ in $CE, DE$ so order $2$ . The orders sum to $12$ , confirming $6$ edges. Exactly two vertices are odd, so the graph is semi-Eulerian.

Tier 2 · Standard

Mark scheme for D1-1.3 Tier 2 · Standard
Question	Scheme	Marks
1	Orders: $A$ is $3$ , $B$ is $3$ , $C$ is $3$ , $D$ is $3$ , $E$ is $2$ , $F$ is $2$ Sum of orders $=16$ , so there are $8$ edges Four vertices have odd order, so the graph is neither Eulerian nor semi-Eulerian $2$ edges must be added For example $AB$ and $CD$ repeated, or $AC$ and $BD$ , since each new edge changes the parity of two vertices	5
(5 marks)		5
Notes
The vertex $A$ lies in $AB, AC, AE$ so has order $3$ ; similarly $B$ is in $AB, BC, BD$ , $C$ is in $AC, BC, CD$ and $D$ is in $BD, CD, DF$ , all of order $3$ ; $E$ is in $AE, EF$ and $F$ is in $DF, EF$ , both of order $2$ . With four odd vertices the graph is neither Eulerian nor semi-Eulerian. Each added edge raises the order of two vertices by one, so it can fix at most two odd vertices, and two added edges suffice: pairing $A$ with $B$ and $C$ with $D$ makes every order even.
2	Each vertex of $K_7$ has order $6$ Number of edges $=\dfrac{7\times6}{2}=21$ Every order is even, so $K_7$ is Eulerian $K_n$ is Eulerian exactly when $n-1$ is even, that is when $n$ is odd The smallest such $n$ greater than $7$ is $9$	5
(5 marks)		5
Notes
In $K_n$ every vertex joins to all $n-1$ others, so each has order $n-1$ and the degree sum is $n(n-1)$ , giving $\frac{n(n-1)}{2}$ edges. For $n=7$ this is order $6$ and $21$ edges, and since $6$ is even $K_7$ is Eulerian. In general $K_n$ is Eulerian when $n-1$ is even, so $n$ must be odd; $K_8$ has odd order $7$ at every vertex, and the next odd value is $n=9$ .
3	Sum of all orders $=2\times13=26$ The seven given orders sum to $25$ The eighth vertex has order $26-25=1$ The odd vertices are the three of order $3$ together with the vertex of order $1$ Four vertices have odd order, so the graph is neither Eulerian nor semi-Eulerian	4
(4 marks)		4
Notes
By the handshaking result the orders sum to twice the number of edges, so the total is $26$ . The seven listed orders sum to $3+3+3+4+4+4+4=25$ , leaving $1$ for the eighth vertex. That gives four odd vertices in all, so the graph is neither Eulerian nor semi-Eulerian.

Tier 3 · Hard

Mark scheme for D1-1.3 Tier 3 · Hard
Question	Scheme	Marks
1	Orders: $A$ is $3$ , $B$ is $3$ , $C$ is $4$ , $D$ is $3$ , $E$ is $3$ Sum of orders $=16$ , so there are $8$ edges Four vertices are odd, so the graph is neither Eulerian nor semi-Eulerian A closed trail needs every vertex even, so the four odd vertices $A$ , $B$ , $D$ , $E$ must be paired Two edges must be repeated	6
(6 marks)		6
Notes
Counting incidences: $A$ appears in $AB, AC, AD$ ; $B$ in $AB, BC, BE$ ; $C$ in $AC, BC, CD, CE$ ; $D$ in $AD, CD, DE$ ; $E$ in $BE, CE, DE$ . The orders are $3, 3, 4, 3, 3$ , summing to $16$ for $8$ edges, and four odd vertices means the graph is neither Eulerian nor semi-Eulerian. Repeating an edge raises the order of both its endpoints by one, so pairing the four odd vertices $A$ , $B$ , $D$ , $E$ into two pairs and repeating one edge for each pair makes every order even; two repeats are therefore the minimum for a closed trail.
2	Sum of orders of $G=18$ , so $G$ has $9$ edges Sum of orders of $H=18$ , so $H$ has $9$ edges The sorted order lists $2, 2, 3, 3, 4, 4$ and $2, 3, 3, 3, 3, 4$ are different Isomorphic graphs have matching orders at corresponding vertices, so $G$ and $H$ are not isomorphic $G$ has exactly two odd vertices, so $G$ is semi-Eulerian $H$ has four odd vertices, so $H$ is neither Eulerian nor semi-Eulerian	6
(6 marks)		6
Notes
Both degree lists sum to $18$ , so each graph has $18\div2=9$ edges; equal edge counts are therefore not enough to decide isomorphism. Isomorphism requires a one-to-one correspondence of vertices preserving order, which forces the sorted degree lists to agree. Here $G$ has two vertices of order $4$ while $H$ has only one, so no such correspondence exists. Counting odd vertices classifies each graph: $G$ has two, so it is semi-Eulerian, while $H$ has four, so it is neither.
3	Sum of orders $=2\times18=36$ $4n=36$ , so $n=9$ Every order is even, so the graph is Eulerian In general the degree sum is $4n$ , so the number of edges is $2n$	5
(5 marks)		5
Notes
By the handshaking result the orders sum to $2\times18=36$ . If all $n$ vertices have order $4$ then $4n=36$ and $n=9$ . Since every vertex has even order and the graph is connected, it is Eulerian. For a general $n$ the same argument gives $4n=2E$ , so $E=2n$ , which indeed returns $18$ when $n=9$ .
4	The orders sum to $2E$ , which is even The even-order vertices contribute an even total, so the odd-order vertices must also contribute an even total A sum of an odd number of odd values is odd, so the number of odd vertices is even With $7$ vertices the number of odd vertices can be $0$ , $2$ , $4$ or $6$ The given orders sum to $1+2+2+3+3+4+5=20$ , so $E=10$ There are four odd vertices, which is allowed, so such a graph can exist	6
(6 marks)		6
Notes
Every edge adds $1$ to the order of each endpoint, so the degree sum equals $2E$ and is even. Splitting the sum into even-order and odd-order vertices, the even part is even, so the odd part must be even too; a sum of odd numbers is even only when there is an even count of them, so three odd vertices are impossible. With $7$ vertices the even counts available are $0, 2, 4, 6$ . The proposed list sums to $20$ , giving $10$ edges, and contains the four odd values $1, 3, 3, 5$ , an even count, so the list passes both necessary tests and no contradiction arises.
5	Sum of orders $=2\times9=18$ The four known orders sum to $12$ , so the orders of $A$ and $F$ sum to $6$ $A$ and $F$ are the two odd vertices, so their orders are odd and sum to $6$ The possible pairs are $(1,5)$ , $(3,3)$ and $(5,1)$ $1$ edge must be added Adding the edge $AF$ makes both orders even, so a closed trail exists	6
(6 marks)		6
Notes
The degree sum is $2\times9=18$ and $4+2+4+2=12$ , so the orders of $A$ and $F$ total $6$ . A semi-Eulerian graph has exactly two odd vertices and its trail runs between them, so $A$ and $F$ are the odd pair; the odd pairs summing to $6$ are $(1,5)$ , $(3,3)$ and $(5,1)$ . Adding a single edge $AF$ raises both orders by one, making every vertex even, so the graph becomes Eulerian and one added edge is enough.

D1-1.4 · The planarity algorithm for planar graphs.

Tier 1 · Easy

Mark scheme for D1-1.4 Tier 1 · Easy
Question	Scheme	Marks
1	A Hamiltonian cycle is a cycle that passes through every vertex of the graph exactly once and returns to its starting vertex A suitable cycle is $ABCDA$	3
(3 marks)		3
Notes
A cycle is a closed path, and a Hamiltonian cycle is one that visits each vertex once and only once before returning to the start. In $K_4$ every pair of vertices is joined, so the edges $AB$ , $BC$ , $CD$ and $DA$ all exist and $ABCDA$ is a Hamiltonian cycle.
2	$AC$ separates $B$ from $D$ , $E$ and $F$ Both $D$ and $F$ lie on the same side of $AC$ , so the chords do not conflict Both chords may be drawn inside, so the graph is planar	3
(3 marks)		3
Notes
With $A, B, C, D, E, F$ around a circle, the chord $AC$ cuts off the single vertex $B$ . The chord $DF$ has both endpoints among $D$ , $E$ , $F$ , on the other side of $AC$ , so the two chords do not cross. With no conflicts at all, both chords can be drawn inside the circle and the graph is planar.

Tier 2 · Standard

Mark scheme for D1-1.4 Tier 2 · Standard
Question	Scheme	Marks
1	$AC$ and $BD$ conflict, because $B$ lies between $A$ and $C$ but $D$ does not $BD$ and $CE$ conflict, because $C$ lies between $B$ and $D$ but $E$ does not $CE$ and $DF$ conflict, because $E$ lies between $D$ and $F$ but $C$ does not There are no other conflicts Labelling: $AC$ inside, $BD$ outside, $CE$ inside, $DF$ outside A consistent labelling exists, so the graph is planar	6
(6 marks)		6
Notes
Place $A, B, C, D, E, F$ around a circle. Chord $AC$ separates $\{B\}$ from $\{D, E, F\}$ ; chord $BD$ separates $\{C\}$ from $\{E, F, A\}$ ; chord $CE$ separates $\{D\}$ from $\{F, A, B\}$ ; chord $DF$ separates $\{E\}$ from $\{A, B, C\}$ . Two chords conflict when exactly one endpoint of the second lies in the set separated by the first, which gives the pairs $AC$ – $BD$ , $BD$ – $CE$ and $CE$ – $DF$ and no others; $AC$ and $DF$ do not conflict, and $AC$ – $CE$ and $BD$ – $DF$ share a vertex. The conflicts form a chain, so alternating labels I, O, I, O works and the graph is planar.
2	$AD$ , $DB$ , $BE$ , $EC$ , $CF$ and $FA$ all join a vertex of $\{A,B,C\}$ to one of $\{D,E,F\}$ , so all six edges exist The cycle visits $A$ , $D$ , $B$ , $E$ , $C$ , $F$ once each and returns to $A$ $K_{3,3}$ has $9$ edges, so the remaining edges are $AE$ , $BF$ and $CD$ $AE$ and $BF$ conflict $AE$ and $CD$ conflict $BF$ and $CD$ conflict	6
(6 marks)		6
Notes
Each consecutive pair in $ADBECFA$ takes one vertex from $\{A, B, C\}$ and one from $\{D, E, F\}$ , so every step is an edge of $K_{3,3}$ , and the six vertices each appear once, making it a Hamiltonian cycle. Since $K_{3,3}$ has $3\times3=9$ edges and the cycle uses six, three chords remain: $AE$ , $BF$ and $CD$ . Reading round the circle $A, D, B, E, C, F$ , the chord $AE$ separates $\{D, B\}$ from $\{C, F\}$ , and $BF$ has $B$ on one side and $F$ on the other, so they conflict; $CD$ has $D$ on one side and $C$ on the other, so it conflicts with $AE$ too; and $BF$ separates $\{E, C\}$ from $\{A, D\}$ , so $CD$ conflicts with $BF$ as well.
3	$AD$ separates $\{B, C\}$ from $\{E, F\}$ , and $BE$ has $B$ on one side and $E$ on the other, so $AD$ and $BE$ conflict $CF$ has $C$ on one side of $AD$ and $F$ on the other, so $AD$ and $CF$ conflict $BE$ separates $\{C, D\}$ from $\{F, A\}$ , and $CF$ has $C$ on one side and $F$ on the other, so $BE$ and $CF$ conflict The three chords conflict in pairs, so no two of them may share a label Three labels would be needed but only inside and outside are available, so the graph is not planar	5
(5 marks)		5
Notes
The three long chords are the main diagonals of the hexagon. Reading round $A, B, C, D, E, F$ , each diagonal separates the other four vertices into two pairs with one endpoint of each remaining diagonal on each side, so every pair of diagonals conflicts. Labelling $AD$ as I forces $BE$ to be O and $CF$ to be O, but $BE$ and $CF$ conflict and cannot share a label, so the algorithm fails and the graph is not planar.

Tier 3 · Hard

Mark scheme for D1-1.4 Tier 3 · Hard
Question	Scheme	Marks
1	$K_5$ has $\dfrac{5\times4}{2}=10$ edges and the cycle uses $5$ , so the chords are $AC$ , $AD$ , $BD$ , $BE$ and $CE$ $AC$ conflicts with $BD$ and with $BE$ $AD$ conflicts with $BE$ and with $CE$ $BD$ conflicts with $CE$ These are all the conflicts; every other pair shares a vertex The conflicts form the five-cycle $AC$ – $BD$ – $CE$ – $AD$ – $BE$ – $AC$ Alternating labels round a cycle of odd length forces two conflicting chords to share a label No consistent labelling exists, so $K_5$ is not planar	8
(8 marks)		8
Notes
With $A, B, C, D, E$ on a circle, $AC$ separates $\{B\}$ from $\{D, E\}$ , $AD$ separates $\{B, C\}$ from $\{E\}$ , $BD$ separates $\{C\}$ from $\{E, A\}$ , $BE$ separates $\{C, D\}$ from $\{A\}$ and $CE$ separates $\{D\}$ from $\{A, B\}$ . Testing each of the ten pairs, the five listed pairs cross and the other five share a vertex. Following the conflicts from $AC$ gives $AC$ as I, $BD$ as O, $CE$ as I, $AD$ as O and $BE$ as I; but $BE$ conflicts with $AC$ , which is also I, a contradiction. The conflicts form a cycle of length five, and a cycle of odd length can never be labelled with two alternating labels, so $K_5$ is not planar.
2	$AC$ separates $\{B\}$ from $\{D, E, F\}$ $AE$ separates $\{B, C, D\}$ from $\{F\}$ $BF$ separates $\{C, D, E\}$ from $\{A\}$ $CE$ separates $\{D\}$ from $\{F, A, B\}$ $AC$ and $BF$ conflict, since $B$ is separated from $F$ by $AC$ $AE$ and $BF$ conflict, since $B$ is separated from $F$ by $AE$ There are no other conflicts, since $AC$ and $AE$ share $A$ , $AC$ and $CE$ share $C$ , $AE$ and $CE$ share $E$ , and $BF$ and $CE$ do not cross Labelling $BF$ outside and $AC$ , $AE$ , $CE$ inside is consistent, so the graph is planar	7
(7 marks)		7
Notes
Place the six vertices round a circle in cycle order. Two chords cross exactly when one endpoint of the second lies in the set the first separates and the other does not. Checking $BF$ against $CE$ : the set separated by $BF$ is $\{C, D, E\}$ , which contains both $C$ and $E$ , so they do not cross. Checking $AC$ against $CE$ and $AE$ against $CE$ : each pair shares a vertex, so neither conflicts. That leaves only $AC$ – $BF$ and $AE$ – $BF$ , both of which cross. The conflict graph is therefore a star centred on $BF$ , which is two-colourable: put $BF$ outside and the other three chords inside.
3	The algorithm redraws a chosen cycle as a circle so that every other edge becomes a chord that lies wholly inside or wholly outside This is only valid when the cycle passes through every vertex, so that no vertex is left off the circle Without a Hamiltonian cycle some vertices would sit inside or outside the circle and their edges could not be classified as simple chords If no Hamiltonian cycle exists the algorithm cannot be applied Failure to apply the algorithm does not prove the graph is non-planar The graph may still be planar and would need a different method, such as an explicit plane drawing	6
(6 marks)		6
Notes
The algorithm turns a plane-drawing question into a two-colouring question by fixing one cycle as a circle and forcing every remaining edge to be a chord drawn on one side or the other. That reduction depends on every vertex lying on the circle, which is exactly the Hamiltonian condition. A graph with no Hamiltonian cycle simply falls outside the method's scope, so the correct conclusion is that the algorithm gives no information, not that the graph fails to be planar; the algorithm proves non-planarity only when it is applied and the conflict labelling is forced into a contradiction.
4	$AC$ separates $\{B\}$ from $\{D, E, F\}$ , $AD$ separates $\{B, C\}$ from $\{E, F\}$ , $BD$ separates $\{C\}$ from $\{E, F, A\}$ , $BF$ separates $\{C, D, E\}$ from $\{A\}$ and $CF$ separates $\{D, E\}$ from $\{A, B\}$ $AC$ and $BD$ conflict $AC$ and $BF$ conflict $AD$ and $BF$ conflict $AD$ and $CF$ conflict $BD$ and $CF$ conflict The conflicts form the five-cycle $AC$ – $BD$ – $CF$ – $AD$ – $BF$ – $AC$ , which has odd length No two-labelling of an odd cycle exists, so the graph is not planar	8
(8 marks)		8
Notes
Reading round $A, B, C, D, E, F$ , a pair of chords crosses when exactly one endpoint of the second lies in the set separated by the first. This gives the five listed conflicts; the remaining pairs $AC$ – $AD$ , $AC$ – $CF$ , $AD$ – $BD$ , $BD$ – $BF$ and $BF$ – $CF$ each share a vertex. Starting from $AC$ as I forces $BD$ to be O, then $CF$ to be I, then $AD$ to be O, then $BF$ to be I; but $BF$ conflicts with $AC$ , which is already I. The conflicts close up into a cycle of five chords, and an odd cycle cannot be two-coloured, so the graph is not planar.
5	$AC$ separates $\{B\}$ from $\{D, E, F, G\}$ $AD$ separates $\{B, C\}$ from $\{E, F, G\}$ $AE$ separates $\{B, C, D\}$ from $\{F, G\}$ $BF$ separates $\{C, D, E\}$ from $\{G, A\}$ $CF$ separates $\{D, E\}$ from $\{G, A, B\}$ Conflicts: $AC$ – $BF$ , $AD$ – $BF$ , $AD$ – $CF$ , $AE$ – $BF$ and $AE$ – $CF$ $AC$ , $AD$ and $AE$ share the vertex $A$ , and $BF$ and $CF$ share the vertex $F$ , so neither of those groups conflicts internally Labelling $AC$ , $AD$ and $AE$ inside and $BF$ and $CF$ outside is consistent, so the graph is planar	8
(8 marks)		8
Notes
Place $A$ to $G$ around a circle in cycle order and read off the set each chord separates. A pair conflicts when exactly one endpoint of the second lies in that set. The chord $AC$ cuts off only $B$ , so it crosses $BF$ but not $CF$ ; $AD$ cuts off $B$ and $C$ , so it crosses both $BF$ and $CF$ ; $AE$ cuts off $B$ , $C$ and $D$ , so it also crosses both. That is all five conflicts, because the three chords at $A$ share a vertex with one another and $BF$ and $CF$ share $F$ . The conflict graph therefore splits into the two groups $\{AC, AD, AE\}$ and $\{BF, CF\}$ with every conflict running between them, so putting the first group inside and the second outside gives a plane drawing.