4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is not necessarily true... Consider an edge e=$v_{1}v_{2}$. Suppose $v_{1}$ and $v_{2}$ each have two other neighbors... Do you see how changing the color of one of them may cause more problems for their neighbors? And therefore, the number of monochromatic edges does not strictly decrease. This is why I mentioned that this approach does not work. $\endgroup$ – MathGuy Apr 2 at 21:11
  • $\begingroup$ @MathGuy Yes, it is always true. Each time you change a color of a "bad" vertex then the number of monochromatic edges does strictly decrease (and may cause more problems for their neighbors but you you have to keep going till the end). $\endgroup$ – Robert Z Apr 3 at 7:29
  • $\begingroup$ @MathGuy Are you still interested in your problem? Is my answer clear now? $\endgroup$ – Robert Z Apr 10 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.