Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
If you write out the details, you'll see that this doesn't work unless you do something like what the Wikipedia proof does. The problem is if $V_1$ has too many edges attached to it, $V_2$ (with the vertices from a matching of $V_1$ removed) doesn't necessarily satisfy Hall's condition. –  Qiaochu Yuan Jun 15 '11 at 17:54

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thank you, both, for hints. I got it now... It is optimal to "pair up" those $k$ vertices from $V_1$ only if they are connected with exactly $k$ vertices in $V_2$, and if there is no such case, then every $k$ vertices from $V_1$ are connected to at least $k + 1$ vertices of $V_2$, and the rest goes on from here. –  user2115 Jun 16 '11 at 0:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.