When a British Mathematical Olympiad (BMO) combinatorics problem describes objects and a relationship between them — friendships, handshakes, shared factors, common properties — the fastest route to a clean proof is often to model the situation as a graph. Vertices represent the objects; edges represent the pairwise relation; and the tools you then reach for are degrees, parity, pigeonhole on vertex degrees, and forced substructures such as triangles, cycles and independent sets.
This article answers a specific reader question for the 2026-27 season: a BMO1 or BMO2 candidate (BMO1 in the China region is scheduled for 19 November 2026; BMO2 for 21 January 2027) is staring at a combinatorics problem and wants to know whether graph theory is the right framework before committing to a long write-up. It supplies a three-question diagnostic, a fully labelled teaching illustration of the six-person Ramsey fact, a degree-sum parity worked check, and a write-up habit that keeps the final answer in the language of the original problem.
Hanlin’s BMO preparation guide lists Graph Theory under BMO2 combinatorics content, alongside the Pigeon-hole Principle and recursive counting (source: “2026 BMO Registration Deadline November 9! G5 STEM Applicants Don’t Miss Out”, Hanlin Course, published 15 October 2026). That listing is the practical starting point: the topic is exam-relevant at the highest round, and the diagnostic below is designed to help you decide whether to use it in any given problem.
Direct Answer: The Three-Question Graph Diagnostic
You should consider a graph model when the answer to all three questions below is yes. If one answer is no, casework, pigeonhole on boxes, or recurrence counting will usually be more direct.
Question 1: Is the relation binary?
A binary relation connects exactly two objects at a time. “A knows B”, “A shares a prime factor with B”, “A and B differ by a perfect square” all qualify. If the problem constraints couple three or more objects simultaneously — for example, “every triple of students contains at least one pair with property X” — the graph formulation is still possible, but the translation may be less clean and should be done carefully before you invest in it.
Question 2: Are you looking for triples, cycles, or independent sets?
Graph theory is strong at detecting structures. If the required conclusion is the existence of three mutually connected objects (a triangle), a closed loop of length k (a k-cycle), or a set of objects with no edges among them (an independent set), those are standard graph concepts and the terminology will carry weight in a proof. “Three mutual acquaintances” translates exactly to “a triangle in the acquaintance graph”.
Question 3: Does each object have a degree, and does the sum of degrees tell you something?
The degree of a vertex is the number of edges incident to it. The Handshaking Lemma — a standard, verifiable result — states that the sum of degrees equals twice the number of edges, so the sum of degrees is always even. If the problem gives you bounds or parity information on the degrees, this lemma often forces a contradiction or pins down a structure. This is the third diagnostic: if you can say something about individual degrees and the total, graph theory will do useful work.
Worked Parity Check: The Number of Odd-Degree Vertices Is Even
Here is a short, fully verified worked check you can reuse inside a BMO proof. Note: this is a teaching illustration, not an actual past BMO question.
Claim: In any finite graph, the number of vertices with odd degree is even.
Proof: Let be a finite graph with vertex set and edge set . By the Handshaking Lemma,
The right-hand side is even. Split the left-hand side into the sum over even-degree vertices and the sum over odd-degree vertices. The sum over even-degree vertices is even. Therefore the sum over odd-degree vertices must be even. Each odd-degree vertex contributes an odd number, so the number of such vertices must itself be even.
How a BMO candidate uses this. If a problem states that every one of people shook hands with an odd number of others, the parity check forces to be even: a graph with odd-degree vertices cannot exist when is odd. If the problem instead states the handshakes form a specific pattern, you can compare the forced parity with the pattern and derive a contradiction. The same argument applies verbatim to vertices representing numbers, sets, cells or regions.
Teaching Illustration: The Six-Person Ramsey Fact
Note: The following is a teaching illustration designed to show the modelling pattern. It is not an actual past BMO question and is not a claim about the BMO syllabus.
Problem: Prove that in any group of six people, there are either three mutual acquaintances or three mutual strangers.
Step 1 — Define the graph. Let the six people be vertices . Draw a red edge between two vertices when the corresponding people are acquaintances, and a blue edge otherwise. Because every pair of distinct people is either acquainted or not, the result is a complete graph whose edges are two-coloured.
Step 2 — Pigeonhole at one vertex. Take any vertex, say . It is joined to the other five vertices by five edges. Each edge is red or blue. By the pigeonhole principle, at least three of those five edges share a colour. Without loss of generality, assume is joined to by red edges. (If instead three were blue, the same argument runs with colours swapped.)
Step 3 — Check the triangle among the neighbours. Examine the three edges among .
- If any one of them is red — say — then are pairwise red, so they form a red triangle: three mutual acquaintances.
- If none of them is red, then all three edges are blue, so form a blue triangle: three mutual strangers.
In either case a monochromatic triangle exists, and the original statement is proved. Note that the translation back to people happens in the final bullet: a red triangle means acquaintances, a blue triangle means strangers. Without that sentence the proof is incomplete.
Proof Habits: Define, Restate, Execute, Translate
Markers award credit for a readable chain of reasoning, not for graph vocabulary alone. Use this four-step pattern so that a reader who does not yet see the graph can follow you.
- Define vertices. State precisely what each vertex represents: “Let the vertices represent the integers to .”
- Define edges. State the exact condition for an edge: “Join two vertices if their difference is a perfect square.”
- Restate the goal in graph language. “We must show the graph contains a triangle” or “we must show the graph has a vertex of degree at least 3.”
- Execute, then translate back. After the graph argument, end with a sentence returning to the original objects: “Therefore there exist three integers whose pairwise differences are perfect squares.”
The translation step is where a technically correct proof often loses clarity marks. Graph mechanics without translation leaves the marker unsure whether you have actually answered the question that was asked.
Common Trap: Forgetting the Translation Back
The most frequent graph-modelling error in olympiad write-ups is ending with “the graph contains a triangle” or “this vertex has degree zero” and never saying what that means for the original people, numbers or cells. Build the translation sentence in advance. If you prove a vertex of degree zero exists, write what that means for the original objects — for instance, “this means one of the participants is connected to nobody in the stated relation”. If you prove a cycle exists, state which objects form the cycle and what role they play.
Comparing Graph Theory with Neighbouring Combinatorics Tools
| Method | Best used when… | Core objects |
|---|---|---|
| Graph theory | Relations are pairwise; the target is a triangle, cycle, matching or independent set; degrees or degree sums carry information. | Vertices, edges, degrees, parity |
| Pigeonhole principle | Objects are being assigned into boxes and you need a collision or a forced count. | Boxes, objects, minimum count |
| Recurrence counting | Configurations build up step by step and you need the total number of valid configurations. | State definition, base cases, transition |
These tools overlap, and the same problem can sometimes be handled by more than one. Graph theory is the natural choice whenever the problem is fundamentally about which pairs satisfy a condition and which do not.
Practical Application in BMO Preparation
Because Hanlin’s BMO preparation guide lists Graph Theory under BMO2 combinatorics content alongside the Pigeon-hole Principle and recursive counting, the most efficient preparation is to practise the translation and parity habits rather than to memorise advanced theorems. During practice, deliberately write out the four-step template above for each problem, then read your write-up back and check whether a reader who has never drawn the graph could still follow the argument.
Two further habits pay off. First, when you see a problem about divisibility between numbers, try vertices for numbers and edges for the divisibility relation — parity of degrees often turns the divisibility condition into a contradiction. Second, when the problem involves geometric incidences (points and lines, circles and chords), try vertices for points and edges for incidences; the same degree-sum argument often applies without modification. For a broader toolkit of BMO1 combinatorics techniques, see the The BMO1 Number Theory and Combinatorics Toolkit: Parity, Invariants, Pigeonhole and the Right Modulus, which places parity, invariants and pigeonhole alongside graph methods.
Two complementary guides are worth reading next. The first explains how to BMO Combinatorics Recurrence: How to Build the State Before Counting — useful when the problem is genuinely about the number of configurations rather than the existence of a substructure. The second explains how to BMO Pigeonhole Principle: Define the Boxes Before Counting the Objects — the right move when the pairwise structure is absent and the problem is about collisions.
Conclusion
Graph modelling is a decision, not a reflex. Ask whether the relation is binary, whether the target is a triangle, cycle or independent set, and whether degrees or the sum of degrees will constrain the answer. When all three answers are yes, define vertices and edges explicitly, run the degree-parity or pigeonhole argument, and close with a translation sentence back to the original objects. That habit — together with the six-person Ramsey pattern above as a template — converts a promising idea into a complete BMO write-up.
General event background is available at Event background.
This is an independent preparation guide, not affiliated with, endorsed by, or sponsored by UKMT.
Frequently Asked Questions
Do I need advanced graph theory to use this in a BMO problem?
No. The useful tools at BMO level are basic: the definition of a vertex and an edge, the degree of a vertex, the Handshaking Lemma (degree sum equals twice the edge count), the pigeonhole principle applied to edges at one vertex, and the ability to detect triangles and independent sets. The difficulty is recognising when to switch to this framework, not in memorising complex theorems.
How do I handle problems with more than two types of relationship?
Use a multi-coloured graph, or build a separate graph for each relation and relate the two. For example, an acquaintance graph and a colleague graph can share the same vertex set. Keep the colour conventions explicit in your write-up and translate each colour back to its meaning in the original problem before concluding.
What if the graph approach seems more complicated than casework?
Re-run the three-question diagnostic. If the relation is not naturally pairwise, or the target is not a triangle, cycle or independent set, and no degree information is available, casework, pigeonhole on boxes or recurrence counting will usually be cleaner. Graph theory is a tool to be chosen when it fits, not a mandatory framework.