- Thread starter
- #1

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].