Ali Tom Martha Michael John Ergatoid In graph terms, our goal is to find a matching for the girls; that is, a subset of edges such that exactly one edge is incident to each girl and at most one edge is incident to each boy. For example, here is one possible matching for the girls Alice Tom Martha Michael John Jane Ergatoid Halls Marriage Theorem states necessary and sufficient conditions for the existence of a matching in a bipartite graph. Hall's Theorem is a remarkably useful mathematical tool, a hammer that bashes many problems. Moreover, it is the tip of a conceptual iceberg,a special case of the"max-flow, min-cut theorem", which is in turn a byproduct of"linear programming duality, one of the central ideas of algorithmic theor We'll state and prove Hall's Theorem using girl-likes-boy terminology. Define the set of boys liked by a given set of girls to consist of all boys liked by at least one of those girls For example, the set of boys liked by Martha and Jane consists of Tom, Michael, and e for us to have any chance at all of matching up the girls, the following marriage con- ition must hold: Every subset of girls likes at least as large a set of boys For example, we can not find a matching if some 4 girls like only 3 boys. Halls The- orem says that this necessary condition is actually sufficient; if the marriage condition holds then a matching exists10 Graph Theory II Martha Alice Sarah Jane Mergatroid Chuck Tom John Michael In graph terms, our goal is to find a matching for the girls; that is, a subset of edges such that exactly one edge is incident to each girl and at most one edge is incident to each boy. For example, here is one possible matching for the girls: Martha Alice Sarah Jane Mergatroid Chuck Tom John Michael Hall’s Marriage Theorem states necessary and sufficient conditions for the existence of a matching in a bipartite graph. Hall’s Theorem is a remarkably useful mathematical tool, a hammer that bashes many problems. Moreover, it is the tip of a conceptual iceberg, a special case of the “max­flow, min­cut theorem”, which is in turn a byproduct of “linear programming duality”, one of the central ideas of algorithmic theory. We’ll state and prove Hall’s Theorem using girl­likes­boy terminology. Define the set of boys liked by a given set of girls to consist of all boys liked by at least one of those girls. For example, the set of boys liked by Martha and Jane consists of Tom, Michael, and Mergatroid. For us to have any chance at all of matching up the girls, the following marriage con￾dition must hold: Every subset of girls likes at least as large a set of boys. For example, we can not find a matching if some 4 girls like only 3 boys. Hall’s The￾orem says that this necessary condition is actually sufficient; if the marriage condition holds, then a matching exists