4
$\begingroup$

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!

0 Answers 0