Matchings without Hall’s theorem

In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding augmenting paths.  Given a matching in a bipartite graph on vertex classes and , an augmenting path is a path from to such that ever other edge of is an edge of …

Matchings and minimum degree

A Tale of Two Halls (Philip) Hall’s theorem.  Let be a bipartite graph on vertex classes , .  Suppose that,  for every , .  Then there is a matching from to . This is traditionally called Hall’s marriage theorem.  The picture is that the people in are all prepared to marry some subset of the …