4
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ Which Gallai's lemma? Which Tutte's theorem? Both these gentlemen proved a nontrivial number of results. $\endgroup$
    – Igor Rivin
    Commented Nov 8, 2012 at 4:24
  • $\begingroup$ @Igor, and @darij: See my edit please. $\endgroup$
    – Tim
    Commented Nov 8, 2012 at 4:42

2 Answers 2

Reset to default
1
$\begingroup$

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.

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

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

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This should be a comment, unless it is going to be turned into an answer. $\endgroup$
    – David Roberts ♦
    Commented Nov 8, 2012 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
    Commented Nov 8, 2012 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
    Commented Nov 8, 2012 at 22:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .