I have a question about the proof of this theorem. If modeled with graphs, theorem would go like this:
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$.
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