Graph two colours, no monochromatic path.

[Arnold1]

I've just begun studying graph theory and I have some difficulty with this problem. Could you tell me how to go about solving it? I would really appreciate the least formal solution possible.

In a graph $$G$$ all vertices have degrees $$\le 3$$. Show that we can color its vertices in two colors so that in $$G$$ there exists no one-color path, whose length is $$3$$.

And a similar one.
There's this quite popular lemma that if in a graph all vertices have degrees $$\ge d$$, then in this graph there's a path whose length is $$d$$.

 

[jza]

There's this quite popular lemma that if in a graph all vertices have degrees $$\ge d$$, then in this graph there's a path whose length is $$d$$.

Let $$v_0 v_1 ... v_k$$ be a path of maximum length in a graph $$G$$. Then all neighbours of $$v_0$$ lie on the path. Since $$\deg (v_0) \geq \delta (G)$$, we have $$k \geq \delta (G)$$ and the path has at least length $$\delta (G)$$.