Gallai's lemma from Tutte's theorem?

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!

• Which Gallai's lemma? Which Tutte's theorem? Both these gentlemen proved a nontrivial number of results. Nov 8 '12 at 4:24
• @Igor, and @darij: See my edit please.
– Tim
Nov 8 '12 at 4:42

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.

• Thanks! If I am correct, (G−x)−(U−x)=G−U if and only if x is in U?
– Tim
Nov 8 '12 at 6:33
• You're welcome and yes you are correct. Nov 8 '12 at 11:27

What would be the definition of $\nu(G)$ in this book?

• This should be a comment, unless it is going to be turned into an answer. Nov 8 '12 at 5:58
• @David Roberts: New users are not allowed to comment until they acquire a small amount of reputation points @Lima: If you answer (or ask) a few questions (likely just one), you'll be able to make comments Nov 8 '12 at 6:18
• I'll edit this with an answer soon. @Tom I was wondering exactly that. Thank you for the info.
– Lima
Nov 8 '12 at 22:42