Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.