26.1. Proof of Hall's Marriage Theorem

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Consider how the vertices are grouped.

2. 2.

   What is Hall's Marriage Theorem?

   Hint

   Think about what the neighbors of a vertex imply.

3. 3.

   What condition is required for a complete matching in Hall's Theorem?

   • |N(A)| ≥ |A| for any subset A
   • |N(A)| < |A| for any subset A
   • |N(A)| = 0

   Hint

   Recall the fundamental statement of the theorem.

4. 4.

   True or False: If there exists a complete matching, the neighbor condition must hold.

   • True
   • False

   Hint

   Think about examples where this relationship applies.

5. 5.

   Prove that in any bipartite graph where |V1| = |V2|, if |N(A)| ≥ |A| holds for all subsets, a complete matching exists.

   Hint

   Break down the proof into base and inductive cases, illustrating graph changes.

6. 6.

   Given a bipartite graph situation, create a scenario where Hall's condition fails and discuss the implications on matchings.

   Hint

   Visualize what happens in your example and analyze neighborhood counts.