OurBigBook.comSite Source code

Hall marriage theorem

A bipartite graph has a matching saturating

X

exactly when

∣ N (S) ∣ \geq ∣ S ∣

for every

S \subseteq X

.

Table of contents 78 2
- Hall induction through a tight set Hall marriage theorem 39
- Regular bipartite graph has a perfect matching Hall marriage theorem 23

 Ancestors (6)

 Incoming links (8)