Skip to main content
4 of 4
add link to book; typed version of the theorem in question for readability/accessibility; rehost image to imgur

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.

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.

Thanks!

Tim
  • 357
  • 1
  • 11