Given a $3$-regular graph $G$, I want to show that I can partition the Vertex set into sets $A,B$ such that each vertex has at most one neighbor within its partition class.
I have come up with two Ideas, but can't bring either one home: One using edge colorings, one using the odd cycle criterion for bipartite graphs. Concerning edge coloring, I thought that if I could find a $3$- edge coloring, maybe I can construct my sets $A,B$ as desired. But then I read about the $3$-regular Petersen graph which is not $3$-edge colorable... Concerning odd cycles, I thought maybe I could break off odd cycles to create a bipartite graph so that adding the deleted edges back still adds at most one "internal" (within $A$ or $B$) edge. But as I said, I haven't gotten anywhere so far...