Welcome to our community

Be a part of something great, join today!

Graph two colours, no monochromatic path.

Arnold

New member
Jan 11, 2013
16
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
Oct 23, 2012
6
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 [tex]v_0 v_1 ... v_k[/tex] be a path of maximum length in a graph [tex]G[/tex]. Then all neighbours of [tex]v_0[/tex] lie on the path. Since [tex]\deg (v_0) \geq \delta (G)[/tex], we have [tex]k \geq \delta (G)[/tex] and the path has at least length [tex]\delta (G)[/tex].