Skip to main content
MathOverflow

Return to Question

add link to book; typed version of the theorem in question for readability/accessibility; rehost image to imgur
Source Link
edit approved May 27, 2014 at 11:21
senshin
edit approved May 27, 2014 at 11:21
senshin
  • 111
  • 5

I have seen a proof of Tutte's theorem from Gallai's lemma. Lovasz also said in his Matching theoryMatching Theory that Gallai's lemma can be easily proven from Tutte's theorem. But I cannot figure out how.

alt text http://i45.tinypic.com/2d98klw.png ThanksMatching 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!

I have seen 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.

alt text http://i45.tinypic.com/2d98klw.png Thanks!

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!

deleted 156 characters in body; edited title
Source Link
Tim
Tim
  • 357
  • 1
  • 11

Proving Gallai's lemma from Tutte's theorem?

I have seen proof of Tutte's theorem from Gallai's lemma. Lovasz also said in his Matching theoryMatching theory that Gallai's lemma can be easily proven from Tutte's theorem. But I cannot figure out how.

alt text http://i45.tinypic.com/2d98klw.png Thanks!

Proving Gallai's lemma from Tutte's theorem?

I have seen 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.

alt text http://i45.tinypic.com/2d98klw.png Thanks!

Gallai's lemma from Tutte's theorem?

I have seen 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.

alt text http://i45.tinypic.com/2d98klw.png Thanks!

added 202 characters in body; deleted 42 characters in body; added 119 characters in body
Source Link
Tim
Tim
  • 357
  • 1
  • 11

I have seen proof of Tutte's theoremTutte's theorem from Gallai's lemma. Lovasz also said in his Matching theoryMatching theory that Gallai's lemma can be easily proven from Tutte's theorem. But I cannot figure out how. Thanks

alt text http://i45.tinypic.com/2d98klw.png Thanks!

I have seen 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. Thanks!

I have seen 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.

alt text http://i45.tinypic.com/2d98klw.png Thanks!

Source Link
Tim
Tim
  • 357
  • 1
  • 11