26.1.2.2.2. Case 2: k-sized Subset with Exactly k Neighbours

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think about how the vertices can be split.

2. 2.

   Define Hall's Marriage Theorem in simple terms.

   Hint

   Focus on the terms 'matching' and 'condition'.

3. 3.

   What is required for a complete matching to exist according to Hall's theorem?

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

   Hint

   Remember the conditions that must hold.

4. 4.

   True or False: A bipartite graph cannot have a complete matching if any subset has fewer neighbours than its size.

   • True
   • False

   Hint

   Think about Hall's necessary condition.

5. 5.

   Construct a bipartite graph with 5 nodes in V1 and 6 in V2, and illustrate a case where Hall's condition does not hold true.

   Hint

   Make sure to check subsets carefully.

6. 6.

   Prove that a complete matching exists in a bipartite graph where every student is guaranteed to have at least 2 job offers.

   Hint

   Think about matching strategies.