Graph two colours, no monochromatic path.

Arnold

New member
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 [TEX]G[/TEX] all vertices have degrees [TEX]\le 3[/TEX]. Show that we can color its vertices in two colors so that in [TEX]G[/TEX] there exists no one-color path, whose length is [TEX]3[/TEX].

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

jza

New member
There's this quite popular lemma that if in a graph all vertices have degrees [TEX] \ge d [/TEX], then in this graph there's a path whose length is [TEX]d[/TEX].
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)$$.