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

Hall's Marriage Theorem and Matchings in Graphs Kam Shan Ho '13
Mathematics and Statistics Department Colloquium

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.

Share
Subscribe
Event Type

lecture/seminar/presentation

Department

Mathematics & Statistics

Recent Activity

People Going

Getting Here