I have seen a proof of Tutte's theorem from Gallai's lemma. Lovasz also said in his Matching Theory that Gallai's lemma can be easily proven from Tutte's theorem. But I cannot figure out how.
3.1.13. THEOREM. (Gallai's Lemma). If graph $G$ is connected and $\nu(G-u)=\nu(G)$ for each $u \in V(G)$, then $G$ is factor-critical.
We remark that an easy proof would follow from Tutte's Theorem, but here we choose a more direct proof based on Corollary 3.1.7.
Thanks!
Gallai's Lemma certainly follows from the somewhat more general Tutte–Berge formula, which easily follows from Tutte's theorem.
Let $G$ be a connected graph such that $\nu(G-u)=\nu(G)$ for all $u \in V(G)$ and let $U$ be a set which gives equality in the Tutte-Berge formula. Suppose $U$ is non-empty and $x \in U$. Evidently, $(G-x)-(U-x)$ has the same set of odd components as $G-U$. By the Tutte-Berge formula, it follows that $\nu (G-x) < \nu (G)$, which is a contradiction. Therefore, $U=\emptyset$. By the Tutte-Berge formula, we have that either $G$ has a perfect matching (if $G$ has an even number of vertices) or a matching covering all vertices except one (if $G$ has an odd number of vertices). Since $\nu(G-u)=\nu(G)$ for all $u \in V(G)$, the first possibility is impossible, and so the second possibility holds. Thus, $G-u$ has a perfect matching for all $u \in V(G)$, as required.
What would be the definition of $\nu(G)$ in this book?
