Maths EE ideas library
Maths Extended Essay ideas: discrete mathematics and graph theory
Graphs, networks, combinatorics and counting. Many questions here can be explored with small cases by hand and then proved in general.
Discrete mathematics and graph theory ideas (10)
- Why five colours are enoughGraph theoryAmbitious
- Routes that use every street onceGraph theoryAccessible
- Ramsey numbers: order in any partyGraph theorySolid
- The Catalan numbers everywhereGraph theorySolid
- Derangements and the hat-check problemGraph theoryAccessible
- Colouring graphs to build timetablesGraph theorySolid
- Why greedy works for spanning treesGraph theoryAccessible
- How good is a quick tour?Graph theoryAmbitious
- Stable matchingsGraph theorySolid
- Surprising results from the pigeonhole principleGraph theoryAccessible
Research questions to start from
One starting question for each idea. Change the case, the comparison or the limit until it is yours.
- Why five colours are enough Ambitious
- How does the five-colour theorem for planar maps follow from Euler's formula, and why is the four-colour case so much harder? A complete proof you can own, set against the famous computer-assisted proof.
- Routes that use every street once Accessible
- When does a network have a route that uses every edge exactly once, and how can the shortest closed route covering every edge be found when it does not? A theorem with a short proof and an algorithm (route inspection) to analyse.
- Ramsey numbers: order in any party Solid
- Why does any party of six people contain three mutual friends or three mutual strangers, and what is known about larger Ramsey numbers? A proof you can explain completely, then bounds that show why the problem gets hard.
- The Catalan numbers everywhere Solid
- Why do bracket sequences, lattice paths and polygon triangulations all give the Catalan numbers? Several bijections and one formula: the argument links them all.
- Derangements and the hat-check problem Accessible
- What is the probability that nobody gets their own hat back, and why does it approach 1/e? Inclusion–exclusion and a recurrence give the same answer, with a surprising limit.
- Colouring graphs to build timetables Solid
- How can graph colouring schedule exams without clashes, and how close does a greedy algorithm come to the minimum number of sessions? Theory (bounds on the chromatic number) and an algorithm evaluated against it.
- Why greedy works for spanning trees Accessible
- Why do Kruskal's and Prim's algorithms always find a minimum spanning tree, and when do they give different trees? Proving an algorithm correct is real mathematics, and the comparison is natural.
- How good is a quick tour? Ambitious
- How close to optimal are the nearest-neighbour and tree-doubling heuristics for the travelling salesperson problem, and what guarantees can be proved? Approximation guarantees are provable statements about algorithms; ideal for analysis and evaluation.
- Stable matchings Solid
- Why does the Gale–Shapley algorithm always produce a stable matching, and why does it favour the side that proposes? An algorithm with elegant proofs of termination, stability and optimality.
- Surprising results from the pigeonhole principle Accessible
- How can the pigeonhole principle prove results such as the Erdős–Szekeres theorem on increasing and decreasing subsequences? A simple principle with a deep result as the target and smaller ones as steps.
Frequently asked questions
Is discrete mathematics and graph theory a good area for a maths EE?
It can be, if you narrow it to one question you can answer with mathematics you understand. Start from small cases you can check by hand, find the pattern, then prove it. Keep a record of the cases: it is evidence for your reflection too.
Can I use one of these research questions as it is?
Use it as a starting point. Change the case, the comparison or the limit until the question is your own, and agree it with your supervisor.
Other areas: Number theory · Algebra · Analysis & calculus · Geometry · Probability · Statistics · Modelling · Codes & algorithms · Optimisation & games · History of maths