6.5 Tutte’s theorem

(Lovasz, 1975) In a $1$-factor, the odd components will have at least one vertex each to be matched to vertices in $S$ and these vertices in $S$ have to be distinct. Thus, $o(G-S)\le |S|$ for all $S\subset V$ if $G$ has a $1$-factor.

Now let $G$ be a graph without $1$-factor. We shall show that there is a bad set i.e., a set $S$ violating Tutte’s condition - $o(G-S)\le |S|$ for all $S\subset V$. If $G^{\prime }=G+e$ has no $1$-factor, then so does $G$. Further if $G^{\prime }$ has a bad set $S$, then so does $G$. Hence, we shall assume that $G$ is an edge-maximal graph without $1$-factor and we shall find a bad set in $G$.

Heuristic: Characterization of Bad sets. If $S$ is a bad set for $G$, then all components of $G-S$ have to be complete. If a component, say $C$, is not complete, we can consider $G\cup e$ where $e$ is a missing edge in $C$. Since $o(G\cup e-S)=o(G-S)>|S|$, by forward implication of the theorem we have that $G\cup e$ does not have a $1$-factor i.e., violating edge-maximality of $G$. Further, by the same reasoning, $s\in S$ must be connected to all vertices in $G-s$. We will now show that these two conditions characterize bad sets and then produce such a set.

Let us say a set $S\subset V$ satisfies condition B if all components of $G-S$ are complete and all $s\in S$ are connected to all vertices in $G-s$.

Claim : Let $G$ have no $1$-factor and be maximal as above. If $S$ satisfies condition B, then either $S$ is bad or $\mathrm{\varnothing }$ is bad.

Proof of Claim: If $S$ is not bad, we shall show that $|V|$ is odd and so $\mathrm{\varnothing }$ is bad. We can join one vertex from each of the odd components to a distinct vertex in $S$ and then try to pair up the remaining vertices. In every even component of $G-S$, we can pair up the vertices and in every odd component too, we can pair up the unpaired vertices to $S$. We are only left with remaining vertices $S^{\prime }\subset S$ where $|S^{\prime }|=|S|-o(G-S)$ and $S^{\prime }$ forms a complete subgraph. But since $G$ does not contain a $1$-factor and there is a complete matching on $V-S^{\prime }$, $S^{\prime }$ cannot have a complete matching and so $|S^{\prime }|$ is odd. Since $|V-S^{\prime }|$ is even, $|V|$ is odd i.e., $\mathrm{\varnothing }$ is a bad set.

Construction of set satisfying Condition B. Now, to show that $G$ has a set $S$ satisfying condition B, let $S$ be the set of vertices such that $s\in S$ is adjacent to every other vertex. If $S$ does not satisfy condition B, then some component of $G-S$ isn’t complete. Let $v\nsim w$ in a component and let $v,v_1,v_2$ be the first three vertices on a shortest path from $v$ to $w$ with possibly $v_2=w$. Then $v\sim v_1,v_1\sim v_2$ but $v\nsim v_2$. Since $v_1\notin S$, by construction of $S$ there is a $u$ such that $u\nsim v_1$. By maximality of $G$, there is a $1$-factor $H_1$ in $G+(v{v}_2)$ and $H_2$ in $G+(v_{1}u)$. Let $P=u\mathrm{\dots }{u}^{\prime }$ be a maximal path in $G$ starting at $u$ with an edge from $H_1$ and alternating between edges in $H_1$ and $H_2$.

If last edge of $P$ is in $H_1$, by maximality of $P$ this implies that there is no edge of $H_2$ incident on $u^{\prime }$ in $G$. This implies that $u^{\prime }=v_1$ as every other vertex has an edge of $H_2$ incident on it in $G$. We will then set $C=Pu$. Note that $C$ is a cycle and it is of even length as $P$ starts in $H_1$ and ends in $H_1$. If the last edge of $P$ is in $H_2$, again by maximality of $P$ this implies that there is no edge of $H_1$ incident on $u^{\prime }$ in $G$ and as earlier, this means $u^{\prime }\in \{v,v_2\}$. Then consider $C=P{v}_{1}u$. Again, $C$ is an even cycle as $P$ starts in $H_1$ and ends in $H_2$. In either case $C$ is an even cycle and $(v_1,u)\in C-E$.

But then consider $H^{\prime }=H_2-(C\cap H_2)+(C-H_2)$ i.e., on $C$ replace the edges of $H_2$ by those of $C-H_2$. Now, $H^{\prime }\subset G$. Since $H_2$ is a $1$-factor, so is $H^{\prime }$ and thus we get a contradiction. Thus $S$ satisfies condition B as required. ∎

Let $G$ contain a subgraph $H$ with a $1$-factor with $|V(H)|=|V(G)|-k$ for some $k\le d$. Consider $G^{\prime }:=G\vee K_k$, the join of $G$ and $K_k$ (i.e., every vertex of $G$ is joined to every vertex of $K_k$). Then $G^{\prime }$ has a $1$-factor by considering $H$ along with a matching between $V(G)-V(H)$ and $K_k$. Let $S\subset V$. Then $o(G^{\prime }-(S\bigsqcup [k]))\le |S|+k$ as $G^{\prime }$ has a $1$-factor. Further, $G^{\prime }-(S\bigsqcup [k])=G-S$ and so $o(G-S)\le |S|+k\le |S|+d$.

Let $o(G-S)\le |S|+d$ for all $S\subset V$ and $d$ is the minimal such number i.e., $d=\max \{o(G-S)-|S|:S\subset V\}$. We will assume $d\ge 1$ else $d=0$ and Tutte’s $1$-factor theorem applies. Suppose $d=o(G-S_0)-|S_0|$ for some $S_0\subset V$. Then the parity of vertices in $V$ is same as that of of $o(G-S_0)+|S_0|$. Since $o(G-S_0)+|S_0|=d+2|S_0|$, the parity of $d$ is also same as that of $o(G-S_0)+|S_0|$ and so $d$ and $|V|$ have same parity i.e., either $d$ and $V$ are both even or both odd.

Let $G^{\prime }:=G\vee K_d$ and by above argument $|V^{\prime }|$ is even. We will show that there exists a $1$-factor in $G^{\prime }$ and this will imply that $G$ contains a subgraph $H$ with a $1$-factor such that $|V(H)|\ge |V(G)|-d$. To show existence of $1$-factor in $G^{\prime }$ we will verify the Tutte’s condition.

Let $S^{\prime }\subset V\bigsqcup [d]$. Suppose that $[d]\setminus S^{\prime }\ne \mathrm{\varnothing }$. Then $G^{\prime }-S^{\prime }$ is connected and hence $o(G^{\prime }-S^{\prime })\le 1\le |S^{\prime }|$ unless $|S^{\prime }|=\mathrm{\varnothing }$. For $S^{\prime }=\mathrm{\varnothing }$, $o(G^{\prime }-S^{\prime })=0$ as $|V^{\prime }|$ is even and $G^{\prime }$ is connected. Suppose $[d]\subset S^{\prime }$. Let $S^{\prime }=[d]\bigsqcup S$ for some $S\subset V$. Hence $G^{\prime }-S^{\prime }=G-S$ and so $o(G^{\prime }-S^{\prime })=o(G-S)\le |S|+d=|S^{\prime }|$. Thus $G^{\prime }$ satisfies Tutte’s condition. ∎

If $G$ has a $f$-factor, then the corresponding edges (all between vertices in $A(v)$ and $A(w)$ for suitable $v\sim w$) in $H$ form a matching and there are $e(v)$ vertices in $A(v)$ that are unmatched. These can be matched arbitarily with vertices of $B(v)$, giving us a $1$-factor of $H$.

Suppose $H$ has a $1$-factor. Remove $B(v)$ and the vertices in $A(v)$ matched to $B(v)$. Now, at each $v$, $A(v)$ has $f(v)$ vertices remaining. If we merge these $f(v)$ vertices and call them $v$, we get a $f$-factor of $G$. ∎