What exactly does the bipartite matching problem require?

Conditions

• Given a bipartite graph.
• Edges represent allowable pairings.
• Goal is to establish a one-to-one pairing for the left vertices.

Reasoning, step by step

1. Identify the left and right sets of vertices.
2. Understand that edges represent compatibility constraints.
3. Assign each left vertex to a unique right vertex such that the pair is connected by an edge.

Example

The instructor says match each girl to a unique compatible boy and adds formally we want a bijection from the girls to the boys that follows edges.

Common misconceptions

• Thinking that it is enough to assign any boy to each girl without requiring uniqueness.
• Believing that the matching does not need to follow the existing edges in the graph.

Watch the explanation

Explore next

• Why formalize matching as an edge-following bijection from girls to boys?
• How does the Compatible Boys & Girls example in the video show a valid matching?