Let $G$ be a graph on $n$ vertices. Suppose each vertex has at most 3 neighbors. Prove that you can color the vertices either red or blue in such a way that each vertex is connected to at most 1 vertex of the same color.
I tried the following approach: Color the vertices randomly. Then look at each vertex, and if it is connected to more than one vertex of the same color, change its color. I was hoping that there would be some monovariant. The one I considered, which is wordy to explain, did not work (I considered the total number of "off" items per vertex).
My second approach was to construct the graph edge by edge, coloring as you go. I think it makes sense to split the vertices up into four partitions: $V_0$, $V_1$, $V_2$, and $V_3$ where a vertex $v$ belongs into $V_i$, 1$\leq i \leq 3$, if $\deg(v)=i$. Then, go through each vertex of $V_{1}$, adding each edge and coloring each pair of vertices opposite colors, etc.... Something along those lines.
Can anyone think of a clever/simple way to prove this? Because, although my second approach probably works, it will require a ton of technical writing. There must be a simpler way to think about this problem.
Follow your first approach: when you see a vertex which is connected to more than one vertex of the same color, change its color. This algorithm terminates because at each step the number of monochromatic edges, which is a non negative integer, strictly decreases (an edge is monochromatic if its two vertices have the same color).
In fact, assume that a vertex $v$ is red and it has at least 2 neighbours red too. Then we change its color from red to blue and we have that:
1) if $\deg(v)=2$ then the number of monochromatic edges decreases by $2$;
2) if $\deg(v)=3$ and the other neighbour is red then the number of monochromatic edges decreases by $3$;
3) if $\deg(v)=3$ and the other neighbour is blue then the number of monochromatic edges decreases by $2-1=1$.
We keep going in this way and, in a finite number of step, the number of monochromatic edges attains a minimal value and we get the desired colored graph.