Coloring a cubic-graph with 2 colors Given a cubic graph, I want to color its vertices in 2 colors (Say A &amp; B).

A vertex is considered "Good" iff the majority of its neighbors is colored differently than that vertex. (For example, vertex colored A has neighbors  A B B is considered Good, and a vertex colored A has neighbors A A B is considered "Bad")

I suggest the following algorithm:


Pick a random uncolored node
Color it in a way that 2 of its neighbors are X, and the last one is Y (Sometimes of course the neighbors are already colored and we determine from that what color the node needs to be and its neighbors also)
Color the node Y


Running this algorithm seems to work, but I couldn't find an example that it doesn't. And even worse - I cannot even understand how to even begin the proof that this algorithm is correct (if at all)

I feel like I need to use the fact that this is a cubic-graph. But I cannot seem to understand how would that help me here.

EDIT (Observations):


It seems that if I get to pick X uncolored nodes, may graph would have at least X "good" nodes (According to the algorithm)
That X would be at least |V|/4 


I want to start by proving that there can be more than |V|/4 "Good" nodes, because in all of my examples there are at least |V|/2 "Good" nodes.
A 2-coloring of a cubic graph in which all vertices are good is known as an unfriendly partition. Such a coloring always exists, and the following algorithm finds it:


Start with an arbitrary coloring, say everything is colored blue.
While there exists a bad vertex: pick some bad vertex, and flip its color.


Why does the algorithm terminate? Consider the number of monochromatic edges. Flipping the color of a bad vertex decreases the number of monochromatic edges. Since there are $1.5n$ edges, the algorithm terminates after at most $1.5n$ steps.

In fact, the entire algorithm can be implemented in $O(n)$ time, essentially since every step only affects $O(1)$ vertices. The basic idea is to maintain a stack or queue of bad vertices.