Sign up ×
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?


share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.