Prove that every 3-regular (simple) graph has Vertex bipartition s.t. each vertex has at most deg=1 within partition class

Question

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

Answer 1

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.

Answer 2

By Brooks's theorem, unless $G$ is the tetrahedral graph $K_4$, its chromatic number $\chi(G)$ is at most $3$. Now take a proper colouring of $G$ where the vertices are coloured blue, white and red.

If a vertex $v$ is red (blue) but

• it has at least two white neighbours
• the neighbours of those neighbours at distance 2 from $v$ are all blue (red)

then recolour $v$ white and its white neighbours red (blue):

Repeat until no more vertices can be recoloured this way; the number of white vertices strictly decreases with each such recolouring, so this process must terminate.

The desired bipartition into vertex sets $U$ and $V$ is then as follows:

• All blue vertices are in $U$
• All red vertices are in $V$
• A white vertex is in the partition corresponding to the minority colour among its neighbours (that is, in $U$ iff it is adjacent to zero or one blue vertices)

For $K_4$, an admissible bipartition can be obtained by placing any two vertices into $U$ and the other two in $V$.