IMO (Maths Olympiad) /Combinatorics

Bipartite Graphs and Matchings

Graph Theory · free study notes

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)

  1. Assume a perfect matching exists.

    • Take any group of students X.
    • They are matched to distinct jobs → at least |X| jobs.
    • So neighbours ≥ |X|.
  2. 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

  1. Bipartite graphs split vertices into two groups; all edges cross groups.
  2. A matching pairs vertices with no overlaps.
  3. Hall’s theorem gives a simple “neighbour count” test for a perfect matching.
  4. 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!

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.