In a graph with edges {(A,1), (A,2), (B,2), (C,3)}, a student claims {(A,1), (A,2)} is a valid matching because both edges exist in the graph. Is this correct?
AYes — any subset of edges in a graph forms a valid matching
BNo — edges (A,1) and (A,2) share vertex A, violating the no-shared-endpoint condition
CNo — a matching must include at least half the edges in the graph
DYes — both edges connect to different right-side vertices (1 and 2), so they are compatible
A matching requires that no two edges share an endpoint — the edges must be vertex-disjoint. Edges (A,1) and (A,2) both involve vertex A, so A would be 'double-booked,' violating the definition. The student's mistake is the most common one: confusing a matching with any subset of edges. Option D describes why the right-side vertices are fine, but the problem is on the left side — vertex A is shared.
Question 2 Multiple Choice
An algorithm has found a matching of size 5 in a bipartite graph, and an exhaustive search confirms that no augmenting path exists. What can you conclude?
AThe matching is maximum — by Berge's theorem, no augmenting path means no improvement is possible
BThe matching may not be maximum; Berge's theorem only applies to perfect matchings
CThe graph must have at least 10 vertices, one for each matched endpoint
DThe matching is maximum only if the graph is connected
Berge's theorem states: a matching M is maximum if and only if there is no augmenting path with respect to M. An augmenting path is a path alternating between unmatched and matched edges, starting and ending at unmatched vertices. If no such path exists, the matching cannot be improved by any strategy — it is definitively maximum. Berge's theorem applies to all matchings, not just perfect ones. Connectivity of the graph is irrelevant.
Question 3 True / False
In a bipartite graph, the maximum matching problem can be solved exactly by formulating it as a maximum flow problem on a network with unit edge capacities.
TTrue
FFalse
Answer: True
This equivalence is a cornerstone result. Construct a flow network: add a source s with unit-capacity edges to every left vertex, direct the bipartite edges from left to right with unit capacity, and add unit-capacity edges from every right vertex to a sink t. A maximum integer flow in this network corresponds exactly to a maximum matching — each unit of flow through the network corresponds to one matched edge. This connection means all max-flow algorithms and the max-flow min-cut theorem apply directly to bipartite matching.
Question 4 True / False
If two matchings in a graph have the same cardinality, then both is expected to be maximum matchings.
TTrue
FFalse
Answer: False
Two matchings can share the same size without either being maximum. For example, in a path graph A–1–B–2–C–3, the matching {(A,1), (C,3)} and the matching {(1,B)} both have different sizes, but consider a graph with multiple components: each component might support non-maximum matchings of equal size without either reaching the global maximum. Matching cardinality equality says nothing about optimality — you must verify the absence of augmenting paths to confirm maximality.
Question 5 Short Answer
What is an augmenting path in the context of bipartite matching, and why does finding one always allow you to increase the size of the current matching?
Think about your answer, then reveal below.
Model answer: An augmenting path is a path in the graph that alternates between edges not in the current matching and edges in the current matching, starting and ending at vertices that are currently unmatched. Because it starts and ends at unmatched vertices and alternates, the path has one more unmatched edge than matched edges. By flipping the matched/unmatched status of every edge along the path — taking in the unmatched edges and removing the matched ones — the matching gains exactly one edge. Berge's theorem guarantees the converse: if no augmenting path exists, the matching is already maximum.
The alternating structure is the key. An augmenting path of length 2k+1 contains k+1 unmatched edges and k matched edges. Flipping produces a new matching of size (original size) + 1. This transforms the combinatorial optimization problem (find the largest matching) into a search problem (find an augmenting path), which is solvable efficiently. Repeated augmentation terminates when no augmenting path remains, guaranteeing maximality by Berge's theorem.