Tutte’s Condition and Its Examples

The Condition and What It Counts

Perfect matching questions in general graphs cannot be settled by checking only whether the graph has an even number of vertices. Deleting a set of vertices may leave several separate components, some of which have odd order; those components each create a local parity obstruction. Tutte’s condition records this information for every possible deletion set. Here we focus on stating the condition precisely and calculating it in several graph families.

All graphs in this tutorial are finite and simple. A component is a maximal connected subgraph. The order of a graph is its number of vertices. For a graph $G$ and a vertex set $S\subseteq V(G)$, $G-S$ is the induced subgraph on $V(G)\setminus S$. A component is odd if its order is an odd integer. We count components, not vertices.

Definition: Write $o(H)$ for the number of odd-order components of a graph $H$, with $o(H)=0$ when $H$ has no vertices. A graph $G$ satisfies Tutte’s condition if $$ o(G-S)\le |S|\qquad\text{for every }S\subseteq V(G). $$

The quantifier includes $S=\varnothing$ and $S=V(G)$. If $S=V(G)$, then $G-S$ is empty, so the inequality reads $0\le |V(G)|$. If $S=\varnothing$, the condition requires that the number of odd components of $G$ be zero. These boundary cases are part of the condition, not optional tests.

The condition is a numerical test on all vertex deletions. It should not be confused with checking just the order of $G$, or just the components of $G$ before any deletion. To use it on a particular graph, specify $S$, find the components remaining after deleting $S$, count the odd ones, and compare that count with $|S|$.

A Parity Fact for Every Deletion

Lemma: For every finite graph $G$ and every $S\subseteq V(G)$, the integers $o(G-S)$ and $|V(G)|-|S|$ have the same parity.

Proof. Let the component orders of $G-S$ be $a_1,\ldots,a_q$, where $q=0$ if $G-S$ is empty. Their sum is the number of remaining vertices: $$ a_1+\cdots+a_q=|V(G)|-|S|. $$ Modulo $2$, each even $a_i$ contributes $0$, and each odd $a_i$ contributes $1$. Therefore the sum has the same parity as the number of odd terms, which is $o(G-S)$. When $q=0$, both sides are zero, so the same conclusion holds. $\square$

In particular, if $G$ satisfies Tutte’s condition, then its order is even: take $S=\varnothing$. The condition gives $o(G)=0$, and the lemma with $S=\varnothing$ says that $|V(G)|$ has the same parity as $o(G)$, hence is even. This is a necessary consequence of the condition, not a replacement for checking all the other sets $S$.

Cycles

Proposition: For $n\ge 3$, the cycle $C_n$ satisfies Tutte’s condition if and only if $n$ is even.

Proof. First suppose $n$ is odd. With $S=\varnothing$, the graph $C_n$ is one odd component, so $o(C_n)=1>0=|S|$. Thus the condition fails.

Now suppose $n$ is even. If $S=\varnothing$, the cycle is a single even component, so $o(C_n)=0\le 0$. If $S=V(C_n)$, then $o(C_n-S)=0\le |S|$. In the remaining case, $S$ is nonempty and some vertices remain. Going around the cycle, the remaining vertices split into consecutive runs separated by deleted vertices. Each run induces a path, so each run is one component of $C_n-S$. Every odd component is one of these runs. The number of runs is at most $|S|$: assign to each run the first deleted vertex following it around the cycle; different runs have different assigned deleted vertices. Hence $$ o(C_n-S)\le \text{number of runs}\le |S|. $$ This proves the condition for every $S$, including the cases already considered. $\square$

Worked Example: Testing an Even Cycle

Let $G=C_6$, with vertex set $V=\{1,2,3,4,5,6\}$ and edge set $E=\{12,23,34,45,56,61\}$. Take $S=\{1,4\}$. Then $|S|=2$, and the remaining graph has vertex set $\{2,3,5,6\}$ and edges $23,56$. Its components are the two paths $2-3$ and $5-6$, both of order $2$. Thus $o(G-S)=0$, and the tested inequality is $0\le2$.

For a second deletion, take $S=\{1\}$. The remaining graph is the path $2-3-4-5-6$, a single component of order $5$. Therefore $o(G-S)=1$, and $1\le |S|=1$. The proposition proves the inequality for every other deletion set as well, so $C_6$ satisfies Tutte’s condition.

Check: with $S=\varnothing$, $C_6$ has one component of order $6$, so $o(C_6)=0\le0$. This agrees with the condition at the empty set.

Worked Example: Refuting the Condition for an Odd Cycle

Let $G=C_5$, with $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. Choose $S=\varnothing$. The remaining graph has one component, the whole cycle, and its order is $5$, which is odd. Thus $o(G-S)=1$, whereas $|S|=0$. The required inequality would be $1\le0$, which is false. A single deletion set that violates the inequality is enough to refute the condition.

Check: the parity lemma gives $o(G)=1$ with the same parity as $|V(G)|=5$. The direct component count and the parity relation agree.

Complete Graphs

Proposition: For $n\ge1$, the complete graph $K_n$ satisfies Tutte’s condition if and only if $n$ is even.

Proof. If $n$ is odd, use $S=\varnothing$: $K_n$ is one odd component, so $o(K_n)=1>0$. Now let $n$ be even and choose any $S\subseteq V(K_n)$. Put $k=|S|$ and $r=n-k$. If $r=0$, the remaining graph is empty and $o(K_n-S)=0\le k$. If $r>0$, the remaining graph is the complete graph $K_r$, hence has exactly one component. Its order is odd precisely when $r$ is odd. In that case $n-k$ is odd; since $n$ is even, $k$ is odd, and therefore $k\ge1$. Thus $o(K_n-S)=1\le k$. When $r$ is even, $o(K_n-S)=0\le k$. The inequality holds for every $S$. For $n=1$, the odd-order case already applies. $\square$

Worked Example: Checking a Complete Graph by Deletion Size

Let $G=K_6$. For a set $S$ of size $k$, the remaining graph is $K_{6-k}$ if $k<6$, and is empty if $k=6$. A nonempty complete graph has one component, which is odd exactly when its order is odd. The calculation for each possible deletion size is:

$k=\|S\|$	Remaining order $6-k$	$o(K_6-S)$	Comparison
0	6	0	$0\le0$
1	5	1	$1\le1$
2	4	0	$0\le2$
3	3	1	$1\le3$
4	2	0	$0\le4$
5	1	1	$1\le5$
6	0	0	$0\le6$

The rows depend only on $k$, not on the identities of the deleted vertices, because every induced subgraph of $K_6$ on $r$ vertices is $K_r$. The table covers every subset size, so it verifies the condition for $K_6$. As an independent check, $K_5$ fails at $S=\varnothing$: its sole component has odd order, giving $o(K_5)=1>0$.

Disconnected Graphs

If a graph is a disjoint union of graphs $G_1,\ldots,G_t$, then for any deletion set $S$, put $S_i=S\cap V(G_i)$. The components remaining in different $G_i-S_i$ cannot join each other, so $$ o(G-S)=\sum_{i=1}^{t}o(G_i-S_i),\qquad |S|=\sum_{i=1}^{t}|S_i|. $$ Consequently, if each $G_i$ satisfies Tutte’s condition, then their disjoint union does too: apply the condition to each $S_i$, add the resulting inequalities, and obtain $o(G-S)\le |S|$. This is a sufficient way to verify the condition for a disconnected graph.

Worked Example: A Disconnected Graph That Satisfies the Condition

Let $G$ be the disjoint union of $C_4$ and $K_2$. Explicitly, take $V=\{1,2,3,4,a,b\}$ and $E=\{12,23,34,41,ab\}$. The cycle $C_4$ satisfies the condition by the cycle proposition, and $K_2=C_2$ is not a cycle under our convention; check it directly. With no vertices deleted, $K_2$ has one even component, so $o(K_2)=0$. Deleting one of its vertices leaves one odd component, giving $1\le1$. Deleting both leaves no component, giving $0\le2$. Thus $K_2$ satisfies the condition.

Since both components satisfy the condition, the sum argument proves it for $G$. For an explicit nonempty test, take $S=\{1,a\}$. The remaining vertices in the cycle component form the path $2-3-4$, of odd order $3$, and the remaining vertex $b$ is an isolated odd component. Hence $o(G-S)=2$, while $|S|=2$, so the inequality is $2\le2$.

Check: at $S=\varnothing$, the two original components have orders $4$ and $2$, both even. Therefore $o(G)=0\le0$.

Worked Example: A Disconnected Graph That Fails

Let $H$ have vertex set $V=\{a,b,c,d\}$ and edge set $E=\{ab\}$. Its components are the edge $ab$ of order $2$, together with the isolated vertices $c$ and $d$, each of order $1$. For $S=\varnothing$, there are two odd components, so $o(H-S)=2$. But $|S|=0$, and $2\le0$ is false. Therefore $H$ does not satisfy Tutte’s condition.

Check: the total order is $4$, which is even, but the condition still fails. Even order alone does not settle the test.

Common Counting Pitfalls

Do not count odd vertices instead of odd components. In the $C_6$ example with $S=\{1\}$, one might incorrectly say that the remaining path has five odd vertices and set $o(G-S)=5$. The definition counts components whose orders are odd, not individual vertices of odd degree or vertices in odd positions. There is one remaining component, of order $5$, so the correct count is $o(G-S)=1$.

Do not test only the empty set. The condition must hold for every $S$. The complete-graph calculation shows that the count can change with the deletion size. Conversely, one failing set is decisive: $C_5$ fails at the empty set without any further calculation.

Keep isolated vertices. An isolated vertex is a component of order $1$, so it contributes one to $o(G-S)$. Forgetting isolated vertices is particularly damaging in disconnected graphs, where they may be the only odd components.

Check Your Understanding

For each question, identify the deletion set being tested and count odd components, rather than odd vertices.

For $C_8$, delete $S=\{1,5\}$. List the remaining components and compute $o(C_8-S)$.
For $K_7$, what is $o(K_7-S)$ when $|S|=4$? Does the inequality hold?
Give a deletion set that shows $C_7$ fails Tutte’s condition, and calculate both sides of the inequality.
Explain why the parity lemma implies that any graph satisfying Tutte’s condition has even order.
Let $G$ be the disjoint union of two copies of $K_2$. Use the componentwise argument to verify that $G$ satisfies the condition.

\(k=\|S\|\)	Remaining order \(6-k\)	\(o(K_6-S)\)	Comparison
0	6	0	\(0\le0\)
1	5	1	\(1\le1\)
2	4	0	\(0\le2\)
3	3	1	\(1\le3\)
4	2	0	\(0\le4\)
5	1	1	\(1\le5\)
6	0	0	\(0\le6\)