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.

Can Hall's theorem be derived from Tutte–Berge formula?

Hall's theorem is for existence of X-saturated matching in a X,Y bipartite graph.

Tutte–Berge formula is for maximum size of a matching:

The theorem states that the size of a maximum matching of a graph $G = (V, E)$ equals

$$\frac{1}{2} \min_{U\subseteq V} \left(|U|-\text{odd}(G-U)+|V|\right).$$

where $odd(H)$ is the number of components in the graph H with an odd number of vertices.

If apply Tutte–Berge formula to a X,Y bipartite graph which has a X-saturated matching, then since the maximum size of a matching is $|X|$, we should have

$$\frac{1}{2} \min_{U\subseteq V} \left(|U|-\text{odd}(G-U)+|V|\right) = |X|,$$

which is equivalent to that $U=X$ maximizes $odd(G-U) - |U|$, at which $odd(G-X) - |X| = |Y|$.

But this is nothing like Hall's condition: for any subset $W$ of $X$, $$ |W| \leq |N(W)|,$$ although I can vaguely and inexplicitly see that they are likely to be equivalent.

So I think Hall's theorem can be derived from Tutte-Berge formula?

Thanks!

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.