Start with the exam
What you need to be able to do
This is the legacy Discrete Mathematics option. Its questions mix integer algorithms, graph traversal, shortest paths, spanning trees and recurrences. The algorithm is part of the answer: show the sequence of choices or reductions so the result can be checked. Do not treat these legacy graph algorithms as compulsory current AA HL revision requirements.
Spend 3 minutes reading the overview and diagram, 7 minutes learning the question patterns, 5 minutes writing out the worked example, and 5 minutes on a bank question or recall check. Take longer when you need to; the full bank is here for later practice.
This collection contains content outside the current course, or a mixture of current and legacy skills. Use the compatibility note for each original question to decide which parts to practise for your exam.
Recognise → set up → write
How the questions are set
Euclidean algorithm and integer equations
Recognise it: Find a greatest common divisor, Bézout coefficients or a modular inverse.
- Repeatedly divide with remainder until the remainder is zero. The last nonzero remainder is the gcd.
- Back-substitute the remainder equations to express the gcd as an integer combination of the original numbers.
- An equation ax+by=c has integer solutions only when gcd(a,b) divides c. For a modular inverse of a modulo m, require gcd(a,m)=1 and reduce the relevant Bézout coefficient modulo m.
Show the division chain and the back-substitution, not only a calculator gcd.
A coefficient can be negative before reducing modulo m. Not every residue has a multiplicative inverse.
Choose the correct graph task
Recognise it: The wording asks to use every edge, visit every vertex, connect everything or find a route.
- An Euler trail uses every edge once; in a connected graph, it has zero or two odd-degree vertices, with an Euler circuit requiring zero. A Hamiltonian path visits each vertex once and uses different reasoning.
- A minimum spanning tree connects all vertices without cycles using n−1 edges. With Kruskal, add cheapest eligible edges while rejecting cycles; Prim grows from an existing connected set.
- Dijkstra finds shortest paths from a source for nonnegative edge weights. Record tentative distances and predecessors, then make the smallest eligible tentative distance permanent.
Name the graph objective and show the successive chosen edges or distance labels.
A shortest-path tree need not be a minimum spanning tree. Euler concerns edges; Hamiltonian concerns vertices.
Solve a linear recurrence
Recognise it: A sequence depends on earlier terms and initial values are supplied.
- For a homogeneous second-order recurrence, try uₙ=rⁿ and form the characteristic equation.
- Distinct roots give a combination Ar₁ⁿ+Br₂ⁿ. A repeated root gives (A+Bn)rⁿ. Use both initial conditions to determine constants.
- For an affine first-order recurrence, find a fixed point and shift the sequence by it to obtain a geometric recurrence. Verify the final formula in both the recurrence and initial values.
Show the characteristic equation or fixed-point shift and the equations for constants.
A repeated root needs the extra n factor; two identical exponential terms do not give two independent constants.
Write it before you reveal it
A worked exam-style example
Original teaching example, created for this lesson.
Original extension example: find gcd(84,30), express it as an integer combination, and find the inverse of 5 modulo 14.
Reveal the worked solution
- 84=2·30+24 and 30=1·24+6, so gcd=6.
- Back-substitute: 6=30−(84−2·30)=3·30−84.
- For the modular inverse, 3·5−14=1, so 5·3≡1 mod 14.
Answer: gcd(84,30)=6=3·30−84; inverse of 5 modulo 14 is 3.
Check: 5×3=15 leaves remainder one on division by fourteen.
From your own collection
Apply it to past-paper questions
These questions anchor the patterns above. Attempt one without the answer, then compare your setup and conclusion with the reasoning. The linked reader contains the source answer and the question-specific syllabus review.
Question 1574
Extended reasoning linking Euclidean algorithm and Bézout coefficients (i), Adjacency multigraph and Euler circuit (ii), Repeated-root recurrence (iii).
Compatibility: Current: (iii)(a): verification; With guidance: (iii): general form and constants; Legacy: (i), (ii), (iv)
View the original question
Original page images preserve the equations and diagrams. Write your response before revealing the reasoning.
Reveal the revision reasoning
- Euclidean divisions give remainders176,80,16,0, so d=16. Back-substitution gives16=−8×256+3×688.
- The adjacency graph is connected and all degrees are even. One Euler circuit is B-E-D-A-B-C-D-F-E-B; a Hamiltonian path is A-B-C-D-E-F.
- Substitute λ^n and nλ^n into the recurrence to verify cancellation. For nonzero λ, the general solution is(A+Bn)λ^n.
- With λ=2,v₁=1,v₂=3, equations2A+2B=1 and4A+8B=3 give A=B=1/4, hence v_n=(n+1)2^(n−2).
- Dijkstra's permanent labels are P0,Q4,W6,R11,U14,V15,S18,T23; record predecessor changes when a shorter tentative route appears.
- Backtracking gives P-Q-W-R-U-S-T with length23.
Editorial revision reasoning. Check the original answer for its marking detail.
Question 1575
Extended reasoning linking Euclidean algorithm and Bézout coefficients (i), Euler versus Hamiltonian traversal (ii), Repeated-root recurrence (iii).
Compatibility: Current: (iii)(a): verification; With guidance: (iii): general form and constants; Legacy: (i), (ii), (iv)
View the original question
Original page images preserve the equations and diagrams. Write your response before revealing the reasoning.
Reveal the revision reasoning
- Euclid gives656=2×272+112,272=2×112+48,112=2×48+16; hence gcd16.
- Reverse these equations to obtain16=−12×272+5×656.
- The connected graph has all degrees even, so B-E-D-A-B-C-D-F-E-B is an Euler circuit. A-B-C-D-E-F is a Hamiltonian path.
- For nonzero λ, verify λ^n and nλ^n directly and combine them as(A+Bn)λ^n. Here λ=3; v₁=2,v₂=9 give A=B=1/3, so v_n=(n+1)3^(n−1).
- Dijkstra labels become permanent in order P0,Q4,W6,R11,U14,V15,S18,T23.
- Predecessors yield P-Q-W-R-U-S-T, total23; T's tentative24 must improve to23 through S before finalization.
Editorial revision reasoning. Check the original answer for its marking detail.
Question 1577
Extended reasoning linking Second-order recurrence (i), Bipartite graphs and isomorphism (ii), Kruskal minimum spanning tree (iii).
Compatibility: Legacy: All parts
View the original question
Original page images preserve the equations and diagrams. Write your response before revealing the reasoning.
Reveal the revision reasoning
- The characteristic equation r²−3r−28=0 has roots−4,7. The initial values give A+B=7,−4A+7B=−6, so x_n=5(−4)^n+2×7^n.
- A bipartite graph partitions vertices into two sets with every edge crossing between them; an isomorphism is an adjacency-preserving vertex bijection. It carries a cycle to a cycle because vertices remain distinct and consecutive adjacency is preserved.
- G is K₃,₃, using alternating vertices around its hexagon as the two parts. H is another drawing of K₃,₃: its parts are{top-left,inner-right,bottom-right} and{top-right,inner-left,bottom-left}. J has a triangle, so cannot be isomorphic to H.
- Kruskal selects CD11,EF21,BD25,AC31,AF51; skip the weight30 edge because it creates a cycle. Total weight is139.
- Well-ordering says every nonempty set of positive integers has a least member. If na≤b for all positive n, equality would immediately fail at n+1, so all b−na are positive.
- A least such difference b−ma is contradicted by the smaller positive b−(m+1)a.
Editorial revision reasoning. Check the original answer for its marking detail.
All 12 questions in this topic
Close your notes first
Can you retrieve the method?
1. Euler versus Hamiltonian?
Check answer 1
Every edge versus every vertex.
2. Edges in a tree with n vertices?
Check answer 2
n−1.
3. When does a modulo m have an inverse?
Check answer 3
When gcd(a,m)=1.
Before you move on
- Identify the requested algorithm before starting.
- Record decisions so the result is reproducible.
- Check recurrence formulas against both initial values and one extra term.
Your revision note
Record one missed cue, one corrected step and one question to retry. Saved only in this browser.