Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm studying Tutte's theorem. There is a proof in Graph Theory / Diestel. I took a very short glance at it before trying to prove it on my own. I am giving my proof attempt here with a specific question.

For a finite graph $G=(V,E)$ and a subset of vertices $S \subset V$, we let $q(S)$ denote the number of connected components of odd size in the graph induced on $V \setminus S$.

Tutte's theorem then says that if $q(S) \leq |S|$ for any $S \subset V$ (I call this Tutte's condition), then there is a perfect matching in $G$.
(the converse is trivially true too).

I'm trying to prove it in the following way: Iteratively remove edges from $G$ without violating Tutte's condition. We get a graph satistying Tutte's condition, for which a removal of any edge would violate Tutte's condition. I claim that all edges are of degree $1$ in this new graph. Thus it is a $1$-factor in the original graph and we are done.

First, vertices of degree $0$ are impossible because they violate Tutte's condition with $S=\emptyset$.

Now, assume there is a vertex $v \in V$ such that $deg(V) \geq 2$. Let $u$ and $w$ be 2 of its neighbours. Thus, removal of either edge $vu$ or $vw$ would result in violation of Tutte's condition. It is thus sufficient to prove the following lemma:

Lemma: For a graph $G=(V,E)$, if removal of edge $vu$ results in violation of Tutte's condition as exhibited by the set $S_1 \subset V$ and removal of edge $vw$ results in violation of Tutte's condition as exhibited by the set $S_2$, then $G$ itself violates Tutte's condition as exhibited by the set $S_1 \Delta S_2 = (S_1 \cup S_2) \setminus (S_1 \cap S_2)$.

Is this lemma true and how can it be proved?

share|cite|improve this question
up vote 2 down vote accepted

Symmetric difference doesn't work. Take the graph $V=\{v,a,b,c\}$, $E=\{va,vb,vc\}$. $G$ violates Tutte's condition but only for $S=\{v\}$, whereas $G\setminus va$ and $G\setminus vb$ both violate it for $\emptyset$.

So let's assume you modify the lemma to allow an arbitrary set for the violation of the condition:

Modified lemma: For a graph $G$ and edges $vu$ and $vw$, if removal of $e$ results in a violation of Tutte's condition for $e=vu$ and $e=vw$, then $G$ violates Tutte's condition.

Then it's not possible to find a counterexample to the general structure of your proof because, assuming Tutte's theorem, the modified lemma is guaranteed to be true for some set depending on $G$: if $G$ satisfies Tutte, $v$ is part of a perfect matching $M$ and so removal of any edge not in $M$ gives a subgraph satisfying Tutte. Therefore, the modified lemma is equivalent to Tutte's theorem.

share|cite|improve this answer
I think there are some mistakes in the first paragraph, nevertheless, this graph is a counterexample. I don't understand the third paragraph. – user3533 Jun 16 '12 at 17:18
I can't see any mistake in the first paragraph. On the other hand, it's true that two edges do suffice, and I clarified the lemma. – Generic Human Jun 16 '12 at 17:30
As for the first paragraph, doesn't removal of $\{a\}$ from $G$ violate Tutte's condition, for example? – user3533 Jun 16 '12 at 17:53
For $S=\{a\}$, there is a single odd connected component ($b-v-c$) so $q(S)=|S|=1$. And when $|S|\ge 2$, $q(S)\le|V\setminus S|\le 2\le|S|$. So $S=\{v\}$ is the only violation. – Generic Human Jun 16 '12 at 23:15
Yes. I see. Thanks for all the help. – user3533 Jun 17 '12 at 7:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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