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)

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