EEDDIITT: Vamos a $C=\{0,1\}^V$ el conjunto de 2-colorantes $f\colon V\to\{0,1\}$.
Cualquier componente conectado de $G$ que consta de un vértice aislado o de dos vértices unidos por una arista, claramente pueden ser ignorados.
Por lo tanto podemos asumir wlog. que $\rho(a)\ge1$ de todos los vértices $a$ $\rho(a)\ge2\lor \rho(b)\ge2$ para todos los bordes $ab$.
Para$f\in C$$S\subseteq V$, vamos
$$ f_S(v)=\begin{cases}1-f(v)&\text{if }v\in S\\f(v)&\text{if }v\notin S\end{cases}$$
ser la coloración obtenida por voltear el color de todos los vértices en $S$.
Para$f\in C$$v\in V$$n\in\mathbb N$, vamos a $S_n(f)$ el conjunto de monocromática de longitud de $n$ rutas, es decir,
$$ 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\}.$$
Vamos
$$N=\min_{f\in C}|S_3(f)|,$$
$$M=\min_{f\in C, |S_3(f)|=N} |S_1(f)|$$
y revisión de la coloración $f\in C$ con $|S_3(f)|=N$, $|S_1(f)|=M$.
Lema 1:
Cada vértice tiene un vecino de diferente color. O: Cada vértice es incidente con un bichromatic borde.
Prueba:
Suponga $a\in V$ sólo tiene vértices del mismo color. Utilizando el hecho de que $\rho(a)\ge1$, vamos a $b$ ser un vecino de $a$.
Deje $g=f_{\{a\}}$.
A continuación,$S_3(g)\subseteq S_3(f)$$S_1(g)\subsetneq S_1(f)$, debido a que cualquier diferencia sólo puede venir de rutas que contienen $a$ y $ab$ ya no es monocromático con la coloración $g$. Entonces $|S_3(g)|\le N$, $|S_1(g)|<M$ contradice minimality de $f$. $_\square$
Lema 2:
Si $ab$ es un borde con $f(a)\ne f(b)$ $a$ tiene un prójimo $c\ne b$ $f(c)\ne f(a)$ o $b$ tiene un prójimo $c\ne a$$f(c)\ne f(b)$. O: Por lo menos un extremo de un bichromatic borde es incidente con otro bichromatic borde.
Prueba:
Asumir lo contrario y deje $g=f_{\{a,b\}}$.
A continuación, $S_3(g)\subseteq S_3(f)$ $S_1(g)\subsetneq S_1(f)$ (para el último en hacer uso de $\rho(a)\ge 2\lor \rho(b)\ge 2$), de nuevo conduce a una contradicción a la minimality de $f$. $_\square$
Teorema: $N=0$.
Prueba:
Asumir lo contrario y deje $(a,b,c,d)\in S_3(f)$ (tenga en cuenta que posiblemente $d=a$, pero $a,b,c$ son distintas).
Por el lema 1, $b$ tiene un prójimo $x$$f(x)\ne f(b)$.
Por el lema 2 aplicado a $bx$, $x$ tiene al menos un vecino de la $y\ne b$$f(y)\ne f(x)$, de ahí en más una vecina $z$$f(z)=f(x)$.
Deje $g=f_{\{b\}}$.
Luego de los bordes $ba$, $bc$ y $bx$ nos enteramos de que $|S_1(g)|=|S_1(f)|-1$, por lo tanto $|S_3(g)|>|S_3(f)|$ por minimality de $f$.
Desde $(a,b,c,d), (d,c,b,a)\in S_3(f)\setminus S_3(g)$, debe haber al menos tres caminos en $S_3(g)\setminus S_3(f)$. De hecho, los caminos siempre vienen en pares (con sus invierte), por lo tanto, debe haber al menos cuatro de estas rutas.
Desde $b$ sólo puede ocurrir como inicio o final, al menos dos rutas de acceso deben empezar a $b$ (y de dos).
Estos tienen necesariamente las formas de $(b,x,z,v)$$(b,x,z,w)$$v\ne w$.
Por definición de $S_3(g)$, vértices $b,x,z$ son distintos. A continuación, $f(z)=g(z)=g(b)\ne f(b)$ y ya $z\ne x$, $z$ no es un vecino de $b$. En consecuencia, $v\ne b$$w\ne b$.
Por lo tanto, $b\notin\{x,z,v,w\}$ $g(x)=g(z)=g(v)=g(w)$ implica $f(x)=f(z)=f(v)=f(w)$, contradiciendo lema 1 (aplicado a $z$). $_\square$
Para el segundo problema, de lo que se escribe acerca de las pruebas a las que tiene poco sentido.
Sin embargo:
Deje $v_0v_1\ldots v_r$ ser un camino de longitud máxima $r$.
Entonces no hay ningún vértice $v_{r+1}$ adyacente a $v_r$ tal que $v_0v_1\ldots v_rv_{r+1}$ es un camino. Es decir: Todas las aristas incidentes con $v_r$ están entre los $r$ bordes $v_0v_1, v_1v_2, \ldots, v_{r-1}v_r$. Esto implica $r\ge d$.
