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…
Best Answer
Choose the bipartition with the most edges crossing from one part to the other.
If there were a vertex with at least $2$ neighbors in the same part, and therefore at most $1$ neighbor in the opposite part, you could move that vertex to the other side and increase the number of crossing edges. But this is impossible, since we started with the bipartition that had the most crossing edges.
So each vertex has at most $1$ neighbor in the same part.