Bipartite Graphs and Matching

Key idea

Pair vertices of two sets using edges.

In depth

A bipartite graph has vertices in two sets with edges only between sets; equivalently, it has no odd cycles. A matching pairs vertices with no overlap. Hall’s theorem gives a condition for perfect matchings.

Worked example

Matching jobs to applicants: edges show which applicant can do which job.

Real-world uses

• Pairing students with projects or drivers with delivery jobs in assignment problems

Common mistake

Assuming a greedy matching is always maximum.

How to learn this

1. Read the key idea and say it in your own words.
2. Work through the worked example, then try a similar problem.
3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

Expand all Collapse all

Related expert topics in Discrete Math & Number Theory

• Strong Induction – Assume all earlier cases to prove the next.
• Well-Ordering Principle – Every nonempty set of positive integers has a least element.
• Partial Orders – Reflexive, antisymmetric, transitive relations.
• Cardinality of Sets – Comparing sizes of infinite sets.
• Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
• Cantor’s Diagonal Argument – Proof that real numbers are uncountable.