2
$\begingroup$

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?

1 Answers 1

2

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.

  • 0
    Yes. I see. Thanks for all the help.2012-06-17