# Looking for counterexample in graph theory

I have this problem from graph theory:

Given a graph $G = (V,E)$ (maybe with multiple edges) find if it's possible to delete some edges such that the new graph is 1-regular (ie. all of its vertices have degree 1).

So far I have only discovered that if number of vertices is odd then it's impossible, this is an easy consequence of the degree formula $\sum_{v \in V} \deg(v) = 2|E|$. Also I can consider there are no multiple edges or loops since I can delete them without affecting the result.

Now if I consider the adjacency matrix of the graph then the resulting adjacency matrix for the new graph must have determinant 1 or -1 because I can get it by permuting the rows/columns of the identity matrix.

I'm guessing two things one bolder than the other. If the number of vertices is even and every vertex has degree at least one it is always possible to get a 1-regular graph and second, if the adjacency matrix of the original graph has determinant 1 or -1 it is possible to delete some edges to get a 1-regular graph. (Maybe deleting edges can be translated to using a pivot to delete some entry in the matrix?)

May someone give me some hints/help or a counterexample to my guessing?

-
I wonder why there's been so many questions on MSE over the last few weeks that use exactly the same convoluted expression to describe "has a perfect matching"... – Erick Wong Jan 11 '14 at 2:08