Complexity of finding even cuts for a graph Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in $V_a$ has an even number of neighbours in $V_b$ and every vertex in $V_b$ has an even number of neighbours in $V_a$? In particular I am interested in the time and depth complexity of solving this problem, or the corresponding decision problem. 

I realise that this may correspond to a well studied problem, and if so I would appreciate a pointer to the relevant literature. It seems closely related to a number of SAT problems, but I have not yet managed to find an exact correspondence.
Such a cut exists if and only if the graph has an even number of spanning trees, which can be checked in polynomial time by using the matrix-tree theorem. See http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf