I have a question about the proof of this theorem. If modeled with graphs, theorem would go like this:
Marriage problem:
Let $V_1$ and $V_2$ be the disjunct set of vertices in a bipartite graph, and let $|V_1| \le |V_2|$. Marriage problem is understood as finding bijection that would map every member from set $V_1$ to some subset of $V_2$.
Halls theorem:
Necessary and sufficient condition for solving marriage problem is that any subset of size $k$ of set $V_1$ ( $1 \le k \le m$, $m = |V_1|$) is connected to at least $k$ vertices from set $V_2$.
Standard proof involves using induction (can be seen on wikipedia). What confuses me is why can't it be proven like this:
- We assume that theorem is valid for all $m$ that are strictly less than $V_1$, and we observe the problem for the case when $m = V_1$.
- We partition set $V_1$ in two subsets smaller than $V_1$. We solve the marriage problem for the first one whose cardinality is $h$ (using assumption).
- Second subset has cardinality of $m – h$, and marriage problem condition is true for this subset as well, so we solve it using assumption again.
What's wrong with this kind of proof. What confuses me in the "standard" proof is assuming that "stronger condition" and using it for some reason…
Wikipedia: Hall's marriage theorem
Best Answer
Here's what you're suggesting. Divide $V_1$ into two subsets $A,B$. Find an injective (one-to-one) mapping $f$ from $A$ to $V_2$. Find an injective mapping $g$ from $B$ to $V_2$. Join together $f,g$ to get an injective mapping from $V_1 = A \cup B$ to $V_2$.
The problem is that while $f,g$ are each injective, they might map some $a \in A$ and some $b \in B$ to the same $v \in V_2$. So $f \cup g$ is not necessarily injective.