Tag: matchings

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 …

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 …