26.1.1. Theorem Statement and Necessary Condition

Theorem Statement: Hall’s Marriage Theorem states that if you have a bipartite graph with bipartition (V1, V2) and if you want to find out whether there exists a complete matching from the subset V1 to subset V2, then it is possible if and only if |𝑁(𝐴)| ≥ |𝐴|, for any subset A ⊆ V1. This condition is both necessary as well as sufficient.

Hall's Marriage Theorem provides a condition for the existence of a matching in a bipartite graph. A bipartite graph is defined as having two distinct sets (V1 and V2) where edges only connect nodes from different sets. The theorem states that to have a complete matching (where every node in one subset is matched to a unique node in the other subset), for any subset A from V1, the number of neighboring nodes in V2 (denoted as N(A)) must be at least as large as the number of nodes in A.

Imagine you have two groups: ten girls and ten boys trying to form pairs for a dance. If a girl (node) can potentially dance with a maximum of three boys, and you want to guarantee all girls get a partner, it must be ensured that at any time the number of available dance partners (boys) is at least equal to the number of girls trying to dance. If, for any group of girls, the boys available to them are fewer than the girls, then the pairing will fail, much like how the theorem asserts the condition must hold for complete matching.

The necessary condition states that complete matching from V1 to V2 is only possible if for any subset A ⊆ V1, the condition |𝑁(𝐴)| ≥ |𝐴| holds true. We proceed to prove this necessary condition.

To prove the necessary condition outlined in Hall's Marriage Theorem, we start with the assumption that a complete matching does exist. This complete matching must pair each vertex in V1 to a vertex in V2. If we consider any subset A of V1, if the matching is to be successful, each vertex in A must have distinct neighbors in V2. Therefore, for every vertex in A, there needs to be at least one unique vertex in V2 connected to it. If |𝑁(𝐴)|, the number of neighbors of A, is less than |𝐴|, at least one vertex in A would necessarily lack a partner, preventing a complete matching.

Consider a dating scenario where each man must have a unique partner to create complete pairs. If a group of boys (V1) selects a subset of girls (V2) but collectively can only match with fewer girls than they are, at least one boy will not get a partner. This illustrates that if there aren't enough girls (neighbors) for each selected boy (subset A), a complete pairing (matching) isn't feasible.

We recall the definition of an 'only if' statement. If the condition after 'only if' is not satisfied, then the occurrence of the situation mentioned before 'only if' cannot happen. Hence the absence of a complete matching implies that certain subsets A must be proven to have less neighbors than members.

The definition of an 'only if' statement signifies that if the condition described is false, the other part must also be false. In the context of Hall's Marriage Theorem, if it were ever the case that |𝑁(𝐴)| < |𝐴| for any subset A, we can conclude that no complete matching can exist. This builds upon our understanding that the existence of matches depends on the fulfillment of the specified neighbor condition.

Think of a classroom scenario where the teacher announces that some students will win tickets to a concert (completing matching), but only if their scores on an exam meet a certain threshold. If a student doesn’t meet the score (condition), they cannot win the ticket (complete match). Hence, if required scores aren't achieved, then certain students will definitely not be part of the winners, exemplifying the logic of the 'only if' statement.

--