26.1.2.2.1. Case 1: k-sized Subset with More Neighbours

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think about how the vertices are connected.

2. 2.

   Define a complete matching.

   Hint

   Consider what it means to cover all vertices in one set.

3. 3.

   What does Hall's Marriage Theorem state?

   • A matching exists if |N(A)| = |A|
   • A matching exists if |N(A)| ≥ |A| for any A
   • A matching exists if all vertices are interconnected

   Hint

   Consider what it means for subsets and their neighbours.

4. 4.

   True or False: If |N(A)| < |A| for any subset A, a complete matching can exist.

   • True
   • False

   Hint

   Think about how many vertices need to be matched.

5. 5.

   Prove Hall’s Marriage Theorem using a specific bipartite graph example and calculating neighbours.

   Hint

   Draw the bipartite graph and label neighbours.

6. 6.

   Construct different bipartite graphs, varying the connections, and identify which meet or violate Hall’s conditions.

   Hint

   Compare neighbour counts with set sizes.