Solution Found!
Halls theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a
Chapter 7, Problem 7.30(choose chapter or problem)
Halls theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a bipartitegraph with boys on the left and an equal number of girls on the right. Halls theorem saysthat there is a perfect matching if and only if the following condition holds: any subset S of boysis connected to at least |S| girls.Prove this theorem. (Hint: The max-flow min-cut theorem should be helpful.)
Questions & Answers
QUESTION:
Halls theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a bipartitegraph with boys on the left and an equal number of girls on the right. Halls theorem saysthat there is a perfect matching if and only if the following condition holds: any subset S of boysis connected to at least |S| girls.Prove this theorem. (Hint: The max-flow min-cut theorem should be helpful.)
ANSWER:Step 1 of 3
For a graph , a bipartite graph is obtained by partitioning the vertices of the graph into two sets and in such a way that all edges have their one endpoint lies in and other endpoint lies in . According to Hall’s theorem, for a bipartite graph with has a perfect matching if and only if: