Let G be a graph with maximum degree 3 Prove that its vertices can be colored by 2
colors (each vertex gets one color) in such a way that there is no path of length two whose 3
vertices all have the same color.
 A: The statement is true even for infinite graphs. It's enough to prove it for finite graphs; the infinite case can be derived from the finite case by imitating any of the proofs of the De Bruijn–Erdős theorem.
Let $G$ be a finite graph. Among all vertex colorings of $G$ with two colors, blue and red, choose one which minimizes the number of "bad edges", that is, edges joining two vertices of the same color. I claim that this coloring does what you want.
Assume for a contradiction that there is a path of length two whose edges are all the same color, say blue. In other words, there is a blue vertex $v$ which which has (at least) two blue neighbors, and at most one red neighbor. If we change the color of $v$ from blue to red, then we lose at least two bad edges, while acquiring at most one new bad edge. Thus the new coloring will have fewer bad edges than before, contradicting the fact that the original coloring minimized the number of bad edges.
A: Strong induction on the number of vertices $n$. The statement is true when $n = 1, 2, 3$.
Let $G$ have $n$ vertices and assume that the statement is true for graphs with $k$ vertices for $k<n$. You can now assume $G$ is connected as when it is not connected, each component has strictly smaller number of vertices and you can colour them appropriately.
If $G$ has a vertex $v$ of degree $1$, then delete it, colour $G\setminus\{v\}$ appropriately. Let $w$ be the neighbour of $v$, give $v$ the colour different from that of $w$ and you're good to go.
If not, then every vertex has degree at least 2, hence $G$ has a cycle $C$. Colour the vertices of $C$ alternately so that $C$ doesn't have a path of length $2$ with all vertices having the same colour.
Remove $C$, and colour the components of $G\setminus C$. Now, while joining $C$ back, suppose a vertex $v\in C$ is connected to a vertex $w$ in component $K$, and that $v$ is coloured red. Swap the colours of $K$ (so red becomes blue and blue becomes red) if necessary so that $w$ is coloured blue and then join it to $v$. This way, there is no "bad path" in $K$ and there can be no bad path involving two vertices (including $v$) from $C$ and one from $K$ or two vertices from $K$ and $v$. So, $G$ has no "bad path".
EDIT: There seems to be a mistake as I haven't used the fact that maximum degree is 3. Anyway, check Graph, two colors, no path length 3
You need maximum degree 3 condition as only then will a $v\in C$ be connected to at most one other vertex and the whole swapping business works.
