Hall's Marriage Theorem and Matchings in Graphs
Wednesday, November 14, 2012 at 1:00pm to 1:45pm
Bronfman Science Center, 106 18 Hoxsey St, Williamstown, MA 01267, USA
Abstract: Is it always possible to match a set of n girls to a set of m boys? We can solve this problem using Hall's Marriage Theorem as it provides a necessary and sufficient condition for existence of matchings in bipartite graphs. We will prove the theorem using augmenting paths, and further explore the application of the theorem in a magic card game.
No recent activity
No activity yet
18 Hoxsey St, Williamstown, MA 01267, USAEnlarge Map