Bipartite Graphs and Matching: Explained with Examples

A bipartite graph is a graph whose vertices can be split into two groups — call them Left and Right — such that every edge joins a Left vertex to a Right vertex, and no edge ever joins two vertices inside the same group. Matching is the art of pairing up vertices: a matching is a set of edges with no shared endpoints, so each vertex is used at most once.

Bipartite graphs matter because so many real pairings are two-sided: workers and jobs, students and projects, applicants and positions. Matching theory answers the key question: can everyone on one side be paired with someone suitable on the other?

Key Concepts

• Bipartition: the split of vertices into two independent sets L and R with all edges crossing between them.
• Characterisation: a graph is bipartite iff it contains no odd-length cycle. Any triangle rules bipartiteness out.
• Matching: a set of edges no two of which share a vertex.
• Maximum matching: a matching with the largest possible number of edges. Perfect matching: one covering every vertex.
• Hall's marriage theorem: a matching covering all of L exists iff every subset S of L is collectively adjacent to at least |S| vertices in R.

How It Works

To test bipartiteness, two-colour by traversal: start anywhere with colour 1, give neighbours colour 2, their neighbours colour 1, and so on. If an edge ever joins two same-coloured vertices, an odd cycle exists and the graph is not bipartite. To find a maximum matching, use augmenting paths: start with any matching, then repeatedly find a path from an unmatched vertex to another unmatched vertex that alternates between non-matching and matching edges — flipping it grows the matching by one edge. When no augmenting path exists, the matching is maximum.

Worked Example

Three workers {W1, W2, W3} and three jobs {J1, J2, J3}. Skills: W1 → J1, J2; W2 → J2; W3 → J2, J3. Check Hall's condition: {W2} has neighbour {J2} (1 ≥ 1); {W1, W2} have {J1, J2} (2 ≥ 2); {W2, W3} have {J2, J3} (2 ≥ 2); all three have {J1, J2, J3} (3 ≥ 3). Every subset passes, so a matching covering all workers exists: W1–J1, W2–J2, W3–J3 — a perfect matching with 3 edges. Now change the skills so W1 and W2 can each do only J1. Then {W1, W2} has just 1 neighbour but size 2 — Hall's condition fails, and indeed only one of them can be matched. The maximum matching then has 2 edges.

Common Misconceptions

• Bipartite does not mean "two disconnected parts". A bipartite graph is usually connected; the two groups are a labelling of vertices, not separate components — every edge runs between the groups.
• Two-colourability is the test, not the definition. A graph is bipartite exactly when it is 2-colourable, which is exactly when it has no odd cycle. All three statements are equivalent.
• Hall's condition must hold for every subset, not just single vertices. Each worker having enough neighbours individually is not enough — the bottleneck is always some group taken together, as the worked example shows.

Real-World Applications

• Job assignment: matching workers to tasks they are qualified for — the original "assignment problem".
• College admissions: matching applicants to programmes with capacities.
• Kidney exchange: donor–patient pairs matched across hospitals use bipartite matching algorithms.
• Timetabling: teachers and class slots paired so every class is covered.

A bipartite graph splits vertices into two sides with every edge crossing between them — equivalently, no odd cycle and 2-colourable. Hall's theorem tells you when a full pairing is possible, and augmenting paths find the biggest one.