Hall’s theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a bipartite graph with boys on the left and an equal number of girls on the right. Hall’s theorem says that there is a perfect matching if and only if the following condition holds: any subset S of boys is connected to at least |S| girls.

Prove this theorem.

Answer rating: 100% (QA)

theorem contains if and only if this means we need to prove in both directions ie 1 if matching exis... View the full answer