I'm trying to derive:
Hall Theorem A bipartite graph G with partition (A,B) has a matching of A $\Leftrightarrow \forall S\subseteq A, |N(S)|\geq |S|$
From this:
Tutte Theorem A graph G has a 1-factor $\Leftrightarrow \forall S\subseteq V(G), q(G-S)\leq |S|$
where $q()$ denotes the number of odd connected components.
The idea of the proof is to suppose true the Tutte's condition for a bipartite graph G and by contradiction suppose that $\exists S\subseteq A,|N(S)|<|S|$
Now consider what happens if we remove from G the vertices of $N(S)$. All the vertex of $S$ become isolated vertex (odd component), and potentially we also have some other odd component, so we know that:
$|S|\leq q(G-N(S))\leq |N(S)|$
where we apply Tutte's theorem in the second inequality. Is this a valid proof?
Best Answer
I see that this question was asked quite a while ago, but it is an excellent result that any student of graph theory should see nonetheless. Many graph theory students don't realise that Tutte's theorem is a generalisation of Hall's theorem. I was fortunate enough to have a professor who showed this in lecture explicitly, and I'm happy to recreate that proof here so that other students of graph theory may see the connection between these theorems. The proof I learned is through a series of lemmas:
Theorem. Hall's theorem follows from Tutte's theorem.
Proof. Let $G$ be a bipartite graph of order $n$ with bipartition $(X, Y)$. Consider the auxiliary graph $H$ obtained from $G$ by adding an extra vertex to the partite set $Y$ if $n$ is odd, then adding all edges between vertices of $Y$ to make $Y$ a clique.
Lemma 1. $G$ has a matching of size $\vert X \vert$ if and only if $H$ has a perfect matching.
Pf. $(\Rightarrow)$ Suppose first that $G$ has a matching of size $\vert X \vert$. Since $G$ is bipartite, each edge of the matching has one endpoint in $X$ and the other in $Y$. Since $H[Y]$ is a clique, we may pair up vertices from $Y$ arbitrarily to complete a perfect matching in $H$ (note that $H$ has even order by construction, so the matching we form is indeed perfect).
$(\Leftarrow)$ Suppose now that $H$ has a perfect matching. Since $H[X]$ is independent (since $G$ is bipartite), a perfect matching in $H$ must use $\vert X \vert$ edges to saturate $X$. These edges form a matching of size $\vert X \vert$ in $G$, proving the desired claim. $\square$
Lemma 2. If $G$ satisfies Hall's condition, $H$ satisfies Tutte's condition.
Pf. Suppose that $G$ satisfies Hall's condition, that is, for any $S \subseteq X, \vert N(S) \vert \geq \vert S \vert$. Let $T \subseteq V(H)$; to verify that $H$ satisfies Tutte's condition, we must show that $o(H - T) \leq \vert T \vert$. Since $H[Y \cap T]$ is a clique, the odd components of $H - T$ are the vertices of $X$ all of whose neighbors lie in $T$, possibly along with $Y - T$ (only if $T$ is chosen so that $\vert Y - T \vert$ is odd). Set $$S = \{x \in X : N(x) \subseteq Y \cap T\}$$ (i.e. the vertices of $X$ which become isolated upon the deletion of $T$ from $H$). Since $G$ satisfies Hall's condition, we have that $$\vert S \vert \leq \vert T \cap Y \vert \leq \vert T \vert,$$ and thus $$o(H - T) \leq \vert T \vert + 1.$$ However, since $H$ is of even order, $o(H - T)$ and $\vert T \vert$ must have the same parity, and we obtain $o(H - T) \leq \vert T \vert$; hence $H$ satisfies Tutte's condition, as was to be shown. $\square$
With the preceding lemmas, the actual proof (that Hall's theorem follows from Tutte's theorem) is nearly immediate. As always, necessity of Hall's condition is obvious (to have a matching which saturates $X$, any subset of $X$ must have at least as many neighbors as elements in order to be completely matched). To see why sufficiency of Hall's theorem follows from Tutte, let $H$ be the auxiliary graph considered throughout this proof. Since $G$ satisfies Hall's condition (by assumption), $H$ satisfies Tutte's condition (lemma 2). Since $H$ satisfies Tutte's condition, it has a perfect matching (by Tutte's theorem). Finally, since $H$ has a perfect matching, we may conclude that $G$ has a matching of size $\vert X \vert$, as desired (lemma 1). This completes the proof. $\square$
Remarks. I'd like to reiterate that this proof is not my own, but one that my graph theory professor presented in lecture some years ago (who knows where they first saw it). I dug up my notebook and have tried to recreate what they showed as faithfully as possible. Hopefully this answer finally satiates your curiosity, and hopefully it is able to help graph theory students in the future see exactly why Tutte's theorem is a generalisation of Hall's theorem. If any of the arguments written here are unclear, don't hesitate to ask me for clarification.