Questions: Matchings in Bipartite Graphs

Question 1

In a bipartite graph with |L| = |R| = 6, the maximum matching has size 5. What can you conclude?

• A. A perfect matching exists — size 5 is close enough to size 6 that it qualifies
• B. A perfect matching does not exist, since at least one vertex on each side is unmatched
• C. A perfect matching does not exist, since at least one vertex on some side is unmatched
• D. You cannot conclude anything about perfect matchings from the maximum matching size alone

Answer: (C)

A perfect matching requires every vertex on both sides to be matched. A maximum matching of size 5 in a 6-6 bipartite graph leaves at least one vertex unmatched on one side. In fact, since matching edges pair one vertex from L with one from R, a matching of size 5 leaves exactly one vertex unmatched on each side — so no perfect matching exists. Note that option B says 'each side,' which is correct for this case.

Question 2

An augmenting path in a matching M alternates between edges not in M and edges in M. What property must it have for it to actually augment (increase) the matching?

• A. It must start and end at matched vertices so that flipping edges doesn't disturb the matching
• B. It must start and end at unmatched vertices so that flipping edges increases the matching size by one
• C. It must contain an even number of edges so that the matching remains balanced after flipping
• D. It must pass through a vertex of maximum degree so that the flip has maximum effect

Answer: (B)

An augmenting path starts at an unmatched vertex in L, alternates between unmatched edges (not in M) and matched edges (in M), and ends at an unmatched vertex in R. When you flip the path — making unmatched edges matched and matched edges unmatched — the path gains one more matched edge than it loses. Both endpoints (previously unmatched) become matched. The net effect is that the matching size increases by exactly one. If the path started or ended at a matched vertex, flipping would not increase the matching size.

Question 3

A perfect matching in a bipartite graph can only exist if |L| = |R|.

• T. True
• F. False

Answer: True

A perfect matching covers every vertex on both sides. Since each matching edge pairs exactly one vertex from L with one from R, a perfect matching must use exactly |L| = |R| edges. If |L| ≠ |R|, the smaller side would be fully matched while the larger side would still have unmatched vertices — violating the definition of a perfect matching. Equal cardinality is necessary (though not sufficient — Hall's condition must also hold).

Question 4

Most maximum matching in a bipartite graph is also a perfect matching.

• T. True
• F. False

Answer: False

A maximum matching is simply the largest possible matching — it may or may not cover all vertices. A perfect matching covers every vertex on both sides. For example, in a bipartite graph where |L| = |R| = 3 but only one worker is qualified for any job, the maximum matching has size 1, not 3. Maximum matching = as many edges as possible given the graph structure; perfect matching = complete coverage. They coincide only when the graph's structure (and Hall's condition) permits it.

Question 5

Why does 'flipping' an augmenting path — switching which edges are in the matching — increase the matching size by exactly one?

Model answer: An augmenting path has k edges and alternates: the first edge is unmatched, the second is matched, and so on. Because the path starts and ends at unmatched vertices, it must have an odd number of edges — (k+1)/2 unmatched edges and k/2 matched edges, so one more unmatched than matched. After flipping, the unmatched edges become matched and the matched edges become unmatched. The net gain is one matched edge. The two previously unmatched endpoints are now matched, and no other vertex's matching status changes.

The parity argument is the key. An augmenting path starts unmatched, so its edge sequence is: unmatched, matched, unmatched, matched, …, unmatched. This odd-length alternation gives exactly one more unmatched edge than matched edge. Flipping converts each unmatched edge to matched and each matched edge to unmatched — so the matching gains one edge net. The algorithm repeats until no augmenting path exists, at which point the matching is maximum (by Berge's theorem).