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!