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.

Matching Theory, by Lovasz and Plummer, p. 89

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.


  • $\begingroup$ Which Gallai's lemma? Which Tutte's theorem? Both these gentlemen proved a nontrivial number of results. $\endgroup$
    – Igor Rivin
    Nov 8 '12 at 4:24
  • $\begingroup$ @Igor, and @darij: See my edit please. $\endgroup$
    – 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.

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

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

  • 2
    $\begingroup$ This should be a comment, unless it is going to be turned into an answer. $\endgroup$ Nov 8 '12 at 5:58
  • 1
    $\begingroup$ @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 $\endgroup$
    – Tony Huynh
    Nov 8 '12 at 6:18
  • $\begingroup$ I'll edit this with an answer soon. @Tom I was wondering exactly that. Thank you for the info. $\endgroup$
    – Lima
    Nov 8 '12 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.