MHB 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).