26.1.1. Theorem Statement and Necessary Condition

Try these first

1. 1.

   Define a bipartite graph.

   Hint

   Think about how vertices are separated.

2. 2.

   What does it mean for a graph to have a complete matching?

   Hint

   Imagine pairing a group of boys and girls at a dance.

3. 3.

   What is the main condition of Hall's Marriage Theorem?

   • |N(A)| < |A|
   • |N(A)| = |A|
   • |N(A)| ≥ |A|

   Hint

   Think about neighbor requirements for matching.

4. 4.

   If there exists a complete matching, can we say Hall's condition holds?

   • True
   • False

   Hint

   Consider how matching pairs must work.

5. 5.

   Given a bipartite graph where V1 = {v1, v2, v3} and V2 = {u1, u2}. If v1 is connected to both u1 and u2, and v2 is only connected to u1, while v3 is connected to both. Determine if a complete matching exists.

   Hint

   Count pairs and check connections.

6. 6.

   Design a bipartite graph that satisfies Hall's condition but does not allow for a complete matching. Explain how.

   Hint

   Think of how connections can visually appear.