Bipartite Graphs & Matchings
Simple, beginner‑friendly notes for the IMO Math Olympiad programme
1. What is a Graph?
- A graph is a set of points (vertices) joined by lines (edges).
- Think of a social network: people are vertices, friendships are edges.
2. Bipartite Graphs
- Two separate groups of vertices, no edge inside a group – all edges go from one group to the other.
- Everyday analogy:
Group A = students
Group B = jobs
Edge = “student can do this job”
Visual cue
A1 A2 A3 B1 B2 B3
| | \ | | |
| | \ | | |
| | \ | | |
All arrows go from left (A) to right (B).
3. Matchings
- A matching is a set of edges with no shared vertices.
- Imagine pairing students with jobs so that nobody has two jobs.
Tiny example
| Students | Jobs | Possible edges |
|---|---|---|
| S1 | J1 | S1–J1 |
| S1 | J2 | S1–J2 |
| S2 | J1 | S2–J1 |
A matching could be {S1–J2, S2–J1}.
(Each student and each job appears at most once.)
4. Why Care About Matchings?
- Practical problems: hiring, scheduling, assigning resources.
- Mathematics: leads to powerful theorems (Hall’s theorem, Konig’s theorem).
5. Hall’s Theorem (informal version)
Statement
In a bipartite graph, a perfect matching (every vertex in the left group is matched) exists iff
for every subset X of the left group, the set of neighbours of X is at least as large as X.
Everyday language
- If you look at any group of students, there must be at least as many jobs available to them as there are students in that group.
- If some group of students has fewer jobs than its size, at least one student will be left unmatched.
6. Quick Proof Idea (no heavy jargon)
-
Assume a perfect matching exists.
- Take any group of students X.
- They are matched to distinct jobs → at least |X| jobs.
- So neighbours ≥ |X|.
-
Conversely, assume neighbours ≥ |X| for every X.
- Build the matching step by step.
- If stuck, look at the stuck students – they form a group X.
- Their neighbours are still enough, so you can “swap” edges and free a spot.
- Continue until everyone is matched.
Because the details involve a bit of bookkeeping, the main takeaway is that the size condition guarantees a perfect pairing.
7. Konig’s Theorem (brief mention)
- In bipartite graphs, the size of the largest matching equals the size of the smallest vertex cover (a set of vertices touching every edge).
- Useful when you want to know how many “resources” are needed to cover all connections.
8. Simple Exercises
| # | Task | Hint |
|---|---|---|
| 1 | Draw a bipartite graph with 4 students and 3 jobs; list all matchings. | Remember no student can take two jobs. |
| 2 | For the graph in #1, check Hall’s condition. | Count neighbours for each subset of students. |
| 3 | Give an example where Hall’s condition fails. | Think of 3 students but only 2 jobs reachable. |
| 4 | Use Konig’s theorem on a small graph (≤5 vertices). | Count a maximum matching; then find a minimum cover. |
9. Key Takeaways
- Bipartite graphs split vertices into two groups; all edges cross groups.
- A matching pairs vertices with no overlaps.
- Hall’s theorem gives a simple “neighbour count” test for a perfect matching.
- Konig’s theorem links matchings to covering edges; useful in optimisation.
These concepts are the backbone of many Olympiad problems involving pairings, schedules, and resource allocation. Practice drawing graphs and checking Hall’s condition – it becomes second nature!