Graph, two colors, no path length 3 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?
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$. In all proofs I've seen so far it only says that since minimal degree of these vertices is $d$, then there exist some vertices whose degree is $d$, and so all others must have degrees greater than $d$. I have no idea how to get path length from this. Could you help me with that, too?
 A: EEDDIITT: Let $C=\{0,1\}^V$ be the set of  2-colourings $f\colon V\to\{0,1\}$.
Any connected component of $G$ that consists of an isolated vertex or of two vertices joined by an edge, can clearly be ignored.
Thus we may assume wlog. that $\rho(a)\ge1$ for all vertices $a$ and $\rho(a)\ge2\lor \rho(b)\ge2$ for all edges $ab$.
For $f\in C$ and $S\subseteq V$, let 
$$ f_S(v)=\begin{cases}1-f(v)&\text{if }v\in S\\f(v)&\text{if }v\notin S\end{cases}$$
be the colouring obtained by flipping the colour for all vertices in $S$.
For $f\in C$ and $v\in V$ and $n\in\mathbb N$, let $S_n(f)$ be the set of monochromatic length $n$ paths, i.e. 
$$ S_n(f)=\left\{(v_0,\ldots,v_n)\in V^{n+1}\mid \forall 0< i\le n\colon\  v_{i-1}v_{i}\in E, f(v_i)=f(v_0), i=n\lor v_{i+1}\ne v_{i-1}\right\}.$$
Let 
$$N=\min_{f\in C}|S_3(f)|,$$
$$M=\min_{f\in C, |S_3(f)|=N} |S_1(f)|$$
and fix a colouring $f\in C$ with $|S_3(f)|=N$, $|S_1(f)|=M$.
Lemma 1:
Every vertex has a neighbour of different colour. Or: Every vertex is incident with a bichromatic edge.
Proof:
Assume $a\in V$ has only vertices of the same colour. Using the fact that $\rho(a)\ge1$, let $b$ be a neighbour of $a$.
Let $g=f_{\{a\}}$.
Then $S_3(g)\subseteq S_3(f)$ and $S_1(g)\subsetneq S_1(f)$ because any difference can only come from paths containing $a$ and in fact $ab$ is no longer monochromatic with colouring $g$. Then $|S_3(g)|\le N$, $|S_1(g)|<M$ contradicts minimality of $f$. $_\square$
Lemma 2:
If $ab$ is an edge with $f(a)\ne f(b)$ then $a$ has a neighbour $c\ne b$ with $f(c)\ne f(a)$ or $b$ has a neighbour $c\ne a$ with $f(c)\ne f(b)$. Or: At least one endpoint of a bichromatic edge is incident with another bichromatic edge.
Proof:
Assume otherwise and let $g=f_{\{a,b\}}$.
Then $S_3(g)\subseteq S_3(f)$ and $S_1(g)\subsetneq S_1(f)$ (for the latter making use of $\rho(a)\ge 2\lor \rho(b)\ge 2$), again leading to a contradiction to the minimality of $f$. $_\square$
Theorem: $N=0$.
Proof:
Assume otherwise and let $(a,b,c,d)\in S_3(f)$ (note that possibly $d=a$, but $a,b,c$ are distinct).
By lemma 1, $b$ has a neighbour $x$ with $f(x)\ne f(b)$.
By lemma 2 applied to $bx$, $x$ has at least one neighbour $y\ne b$ with $f(y)\ne f(x)$, hence at most one neighbour $z$ with $f(z)=f(x)$.
Let $g=f_{\{b\}}$.
Then from the edges $ba$, $bc$ and $bx$ we learn that $|S_1(g)|=|S_1(f)|-1$, hence $|S_3(g)|>|S_3(f)|$ by minimality of $f$.
Since $(a,b,c,d), (d,c,b,a)\in S_3(f)\setminus S_3(g)$, there must be at least three paths in $S_3(g)\setminus S_3(f)$. In fact, paths always come in pairs (with their reverses), hence there must be at least four such paths.
Since $b$ can only occur as start- or endpoint, at least two paths must start at $b$ (and two end there).
These necessarily have the forms $(b,x,z,v)$ and $(b,x,z,w)$ with $v\ne w$.
By definition of $S_3(g)$, vertices $b,x,z$ are distinct. Then $f(z)=g(z)=g(b)\ne f(b)$ and since $z\ne x$, $z$ is not a neighbour of $b$. Consequently, $v\ne b$ and $w\ne b$.
Therefore $b\notin\{x,z,v,w\}$ and $g(x)=g(z)=g(v)=g(w)$ implies $f(x)=f(z)=f(v)=f(w)$, contradicting lemma 1 (applied to $z$). $_\square$

For the second problem, what you write about the proofs makes little sense.
However:
Let $v_0v_1\ldots v_r$ be a path of maximal length $r$. 
Then there is no vertex $v_{r+1}$ adjacent to $v_r$ such that $v_0v_1\ldots v_rv_{r+1}$ is a path. That is: All edges incident with $v_r$ are among the $r$ edges $v_0v_1, v_1v_2, \ldots, v_{r-1}v_r$. This implies $r\ge d$.
