Perfect spanning forests

Let $G=([n],E)$ be an undirected graph on $[n]=\{1,\ldots,n\}$; the number $n$ of its vertices is the order of $G$. Recall that a subgraph $H$ of $G$ is an induced subgraph if for every two vertices $i$ and $j$ of $H$, $\{i,j\}$ is an edge of $G$ iff $\{i,j\}$ is an edge of $H$. That is, $H$ is obtained from $G$ by removing some vertices (with all incident edges).

A forest in $G$ is a subgraph $F\subseteq E$ of $G$ without cycles, and is a spanning forest of $G$ if the edges of $F$ touch every vertex of $G$, that is, if every vertex $x\in [n]$ has a nonzero degree in $F$. Connected components of $F$ are trees. If $F$ has only one connected component (is itself a tree), then $F$ is a spanning tree of $G$. A spanning forest $F$ of $G$ is perfect if

the degree of each vertex $x\in [n]$ in $F$ is odd, and
each tree of $F$ is an induced subgraph of $G$.

An example of a perfect spanning forest is a a perfect matching.

By the Handshaking Lemma (Sect. 1.4 in the book), the number of vertices of odd degree in any graph is even. So, if a connected graph $G$ has a perfect spanning forest, then $G$ is of even order: by the Hanshaking Lemma, graphs with all vertices of odd degree must have an even number of vertices. Alex Scott [1] proved that surprisingly the opposite implication is also true, that is, every connected graph $G$ of even order contains a perfect spanning forest. The proof is graph-theoretical and relatively long. Gregory Gutin [2] has found an amazingly simple proof using the linear algebra method.

Perfect Forest Theorem (Scott [1]): Every connected graph of even order contains a perfect spanning forest.

Proof (due to Gutin [2]): Let $n\geq 2$ be an even integer, and let $G=([n],E)$ be a connected graph on $[n]=\{1,\ldots,n\}$. Our goal is to show that $G$ must contain at least one perfect spanning forest. Associate with every edge $e=\{i,j\}$ of the complete graph $K_n$ on $[n]$ the vector $v_e\in\FF^n$ with exactly two $1$s in positions $i$ and $j$.¹ A simple but important observation is that a set of edges contains a cycle if and only if the corresponding set of vectors is linearly dependent; we are working over $\FF$.

Since the graph $G$ is connected, it has a spanning tree $T$. Since $T$ has no cycles, the vectors $v_e$ for $e\in T$ are linearly independent. Since addition of an edge $e\in E\setminus T$ to the tree $T$ closes a cycle, for every edge $e\in E\setminus T$, the vector $v_e$ is a sum of some vectors $v_f$ for $f\in T$.

Since $n$ is even, there is a perfect matching in $K_n$, say $\{1,2\},\{3,4\},\ldots,\{n-1,n\}$. The sum of the corresponding to these edges vectors gives the all-$1$ vector $\vec{1}$. Each of these vectors $v_{\{i,i+1\}}$ either belongs to the set $\{v_e\colon e\in T\}$, if $\{i,i+1\}$ is an edge of $T$, or is a linear combination of some vectors of this set, if the addition of the edge $\{i,i+1\}$ to the tree $T$ forms a cycle in $G$. So, there is a linearly independent subset $L\subseteq \{v_e\colon e\in T\}$ of vectors associated to the edges of the tree $T$ summing up to the all-$1$ vector $\vec{1}$. Let $M=\{v_e\colon e\in E\}$ be the set of all vectors associated to the edges of the entire graph $G$. For each vector $v_e\in M\setminus L$, the extended set $\{v_e\}\cup L$ is either linearly dependent or remains linearly independent.

Case 1: The set $\{v_e\}\cup L$ is linearly dependent for some $v_e\in M\setminus L$. Then the vector $v_e$ is a sum of some $ \geq 2$ vectors from $L$. So, if we remove these vectors from $L$, and add the vector $v_e$ to $L$, then we have a shorter expression of the vector $\vec{1}$ as the sum of the vectors in the resulting set.

Case 2: The set $\{v_e\}\cup L$ is linearly independent for all $v_e\in M\setminus L$. Consider the graph $F$ consisting of all edges $e$ with $v_e\in L$. We claim that then $F$ is a (desired) perfect spanning forest of $G$. As the set $L$ of vectors associated with the edges of $F$ is linearly independent, the graph $F$ has no cycles. So, $F$ is a forest. Since the sum mod 2 of vectors in $L$ is $\vec{1}$, every vertex $x\in [n]$ has odd degree in $F$; in particular, $F$ is a spanning forest of $G$. Now let $T'$ be a connected component of $F$ (a tree). We have to show that $T'$ is a induced subgraph of $G$. Assume to the contrary that there are two vertices $i$ and $j$ such that $e=\{i,j\}$ is an edge of $G$ but not of $T'$. Then $T'\cup\{e\}$ contains a cycle, meaning that the extended set $\{v_e\}\cup \{v_f\colon f\in T'\}\subseteq \{v_e\}\cup L$ is linearly dependent, a contradiction.

Since $|L|\leq n$ and Case 1 produces a shorter expression for the vector $\vec{1}$, after at most $n$ iterations of Case 1 we will arrive at Case 2, which gives us a desired perfect spanning forest of $G$. $\Box$

Remark: Note that the argument only uses two properties:

the graph $G$ has a spanning tree (since $G$ is connected);
some set of vectors associated with the edges of $K_n$ sums up to $\vec{1}$ (since $n$ is even).

Proof by induction

In the paper [3], Yair Caroa, Josef Laurib, and Christina Zarb give a yet another short proof of the Perfect Forest Theorem, this time via induction on the number $n$ of vertices of $G$. It uses the following simple lemma.

Lemma 1: Let $G=(V,E)$ be a connected graph on $n$ vertices where $n$ is even, and $G$ is not a tree. Then $G$ has a spanning tree with at least two vertices of even degree.

Proof: Let $T$ be a spanning tree of $G$. As the total number $n$ of vertices in $T$ is even, the number of vertices of even degree in $T$ must be even.² If there are at least two such vertices, then we are done. So, assume that that all vertices of $T$ have odd degree. Since $G$ is not a tree, there must be at least one edge $e=\{u,v\}$ in $E\setminus T$. Consider the tree $T'$ obtained from $T$ by adding the edge $e$ and deleting the edge connecting $u$ to $w$ where $w$ is the unique neighbour of $u$ on the path from $u$ to $v$ in $T$. Then the degrees of $v$ and $w$ are now even: the degree of $w$ is decreased by one, and the degree of $v$ is increased by one. So, the spanning tree $T'$ is as required. $\Box$

Inductive proof of Perfect Forest Theorem [3]: Let $G$ be a connected graph on an even number $n$ of vertices. Our goal is to show that $G$ contains a perfect spanning forest. For $n=2$, the theorem is clearly true. So suppose $n\geq 4$ is even. If $G$ is a tree with all degrees odd, then we are done: $G$ itself is the required perfect forest. So, it remains to consider the remaining two cases.

Case 1: $G$ is a tree with at least one vertex $w$ of even degree. Let $\{w,v_1\},\ldots,\{w,v_t\}$, $t$ even, be the edges of $T$ incident to $w$, and $V_1,\ldots,V_t$ be the sets of vertices of the subtrees of $T$ rooted at $v_1,\ldots,v_t$. All $|V_i|$ cannot be odd because then $G$ would have an odd number of vertices: $n=1+|V_1|+\cdots+|V_t|$ would then be an odd number. So, at least one of the sets, say $V_1$ contains an even number of vertices. Let $G_1$ be the induced subgraph of $G$ on $V_1$, and $G_2$ the subgraph induced by the set $\{w\}\cup V_2\cup \cdots \cup V_t$. Clearly, $G_1$ and $G_2$ are both connected and have even order. Hence, by the induction hypothesis, there exist perfect spanning forests $F_1$ and $F_2$ of $G_1$ and $G$ respectively. Thus, $F_1\cup F_2$ is a perfect spanning forest of $G$.

Case 2: $G$ is not a tree. Then by Lemma 1, $G$ has a spanning tree $T$ with at least two vertices of even degree. Let $w$ be any one of these even degree vertices, and use the same argument as in Case 1 to split $G$ into two vertex-disjoint connected components $G_1$ and $G_2$ each of even order. Applying the induction hypothesis on both components gives a perfect forest. $\Box$

^{1.The matrix $A(G)$ whose rows are labelled by vertices, columns by edges of $G$, and where the $e$-th column is the vector $v_e$ is known as the incidence matrix of the graph $G$. This concept was used by Kirchhoff already in 1847. Thus, the sum (over the reals) of the entries in the row of a vertex $x$ is the degree of $x$ in $G$. By the Handshaking Lemma, the sum of all columns over the field $\FF$ is the all-$0$ vector $\vec{0}$. So, the binary rank of $A(G)$ is $\leq n-1$, with the equality iff the graph is connected. [jump back]}

^{2. By the Handshaking Lemma (Sect. 1.4 in the book), the number of vertices of odd degree must be even. Since the total number $n$ of vertices in our case is even, the number of vertices of even degree must be even as well.
[jump back]}

References:

A. D. Scott, On induced subgraphs with all degrees odd. Graphs and Combinatorics, 17 (2001), 539-553.
G. Gutin, Note on perfect forests. Journal of Graph Theory, 83:2 (2016), 233-235.
Y. Caro, J. Lauri and Ch. Zarb, Two short proofs of the Perfect Forest Theorem. Theory and Applications of Graphs, Vol. 4, Iss. 1 (2017), Article 4. arXiv:1612.05004.

S. Jukna, January 2021