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 an 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 an 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.

Prof Gregory Gutin received his PhD in Mathematics in 1993 from Tel Aviv University under the supervision of Noga Alon. Since September 2000 Gutin has been Professor in Computer Science at Royal Holloway, University of London. Gutin's research interests are in graph theory and combinatorial optimization, algorithms and complexity, and information security. He has over 250 papers published or accepted for publication in refereed journals and conference proceedings. In particular, he co-authored with Joergen Bang-Jensen two editions of a monograph “Digraphs: Theory, Algorithms and Applications”. Gutin was the recipient of the Royal Society Wolfson Research Merit Award in 2014, and the best paper awards at ACM Symposium on Access Control Models and Technologies (SACMAT) 2015, 2016 and 2021. In 2017 Gutin became a member of Academia Europaea. In 2021 he was elected Fellow of AAIA (Asia-Pacific Artificial Intelligence Association).