Let $G$ be a graph on $n$ vertices. For $i\in \{0,1\}$ and a connected graph $G$, a spanning forest $F$ of $G$ is called an $i$-perfect forest if every tree in $F$ is an induced subgraph of $G$ and exactly $i$ vertices of $F$ have even degree (including zero). An $i$-perfect forest of $G$ is proper if it has no vertices of degree zero. Scott (2001) showed that every connected graph with even number of vertices contains a 0-perfect forest. A short proof of Scott's theorem using basic linear algebra was obtained by Gutin (2016) and two short graph-theoretical proofs were given by Caro et al. (2017). Intuitively it is clear that a 0-perfect forest can provide a useful structure in a graph and, in particular, this notion was used by Sharan and Wigderson (1996) to prove that the perfect matching problem for bipartite cubic graphs belongs to the complexity class NC.
In my talk, I'll present the linear-algebraic proof and give an overview of the following recent results obtained together with Anders Yeo.
We proved that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges. Moreover, we showed that to decide whether $G$ has a 0-perfect forest with at least $n/2+k$ edges, where $k$ is the parameter, is W[1]-hard. We also proved that for a prescribed edge $e$ of $G$, it is NP-hard to obtain a 0-perfect forest containing $e$, but one can decide if there exists a 0-perfect forest not containing $e$ in polynomial time. It is easy to see that every connected graph with odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We gave a characterization of when a connected graph has a proper 1-perfect forest.