Maximum Matching in Bipartite Graphs

How to read this

• V (top, blue rings) and U (bottom, purple rings) are the two sides; every edge must join the sides. That is exactly a 2-coloring — possible if and only if the graph has no odd-length cycle.
• Green vertices/edges are matched; dashed rings are free vertices.
• A label ←w means "reached from w". U vertices are labeled from V along non-matching edges; a V vertex is labeled from its mate along a matching edge.
• When a free U vertex is reached, the labels trace an augmenting path back to a free V vertex. Flipping it (orange edges in, purple edges out) grows the matching by one.
• The queue chips show BFS order; ↑ marks dequeued vertices, as in Levitin's Figure 10.10.

Try this

1. Textbook graph from M = {(4,8), (5,9)}: predict the three augmenting paths. The third, 3–8–4–10, ends in a different maximum matching than the "obvious" one — maximum matchings need not be unique.
2. Lesson graph from the empty matching: the last augmentation is the 7-edge path 2–5–1–6–3–7–4–8. Every TA moves one section to the right to make room for TA 2.
3. Turn on ✏️ edit and add edge 1–2 in the textbook graph. The 2-coloring check finds the odd cycle 1–2–6 (triangle) and refuses to run. Remove 2–6 instead of 1–2: now it's bipartite again — press "Re-split sides".
4. Load Domino chain: 3 of 4 already matched, yet no single edge can be added. Watch the BFS walk the whole chain to find the one 7-edge augmenting path.
5. Watch the flow network while an augmenting path is shown: s → free V vertex, alternating forward/backward edges, then → t. It is the max-flow labeling algorithm in disguise.