Para un determinado $G$ para que $\chi(G) = \chi_1(G)$, la primera revisión adecuada para colorear con $\chi$ colores. Deje $G_i$ el conjunto de vértices de color $i$. Deje $E(i,j)$ ser el número de aristas entre $G_i$ e $G_j$. Tenga en cuenta que si por cualquier $i, j$, hubo menos de dos bordes entre las $G_i$ e $G_j$, entonces se podría disminuir el número de colores para colorear $G_i$ color $j$, y no sería en más de una arista que conecta los vértices del mismo color. Por lo $E(i,j) \ge 2$ para todos los pares de $i,j$.
Siguiente, supongamos que para algunos $i,j$ tenemos $E(i,j) < 4$. Si los bordes entre las $G_i$ e $G_j$ eran parejas que no sean adyacentes, entonces otra vez, podríamos simplemente color $G_i$ color $j$, y los bordes de conectar los vértices del mismo color sería pares no adyacentes. Por lo que podemos ignorar esos casos. Esto deja a los cuatro casos posibles:
Caso 1: $a \in G_i, x,y \in G_j, ax, ay \in E$ (el conjunto de borde de $G$)
Caso 2: $a,b \in G_i, x,y,z \in G_j, ax,ay,bz \in E$
Caso 3: $a,b \in G_i, x,y \in G_j, ax,ay,by \in E$
Caso 4: $a \in G_i, x,y,z \in G_j, ax,ay,az \in E$
Se observa que en ninguno de los cuatro casos, si alguno de $x, y$ o $z$ se cambiaron a un color diferente del de $i$ o $j$, entonces los bordes de $G_i$ podría cambiar a otros colores, mientras que el mantenimiento de un 1-inadecuado para colorear. En los casos 1 y 2, se puede colorear todos los de $G_i$ color $j$. En el caso 3, si $x$ o $y$ es cambiado a color $k$, entonces podemos cambiar $a$ color $k$ y todos los otros vértices de $G_i$ color $j$. En el caso 4, si $x,y,$ o $z$ el cambio en el color de $k$, podemos cambiar $a$ color $k$ y el resto de $G_i$ color $j$.
Por lo tanto, debe ser imposible cambiar a $x$ e $y$ a partir de los anteriores a los diferentes colores. Eso significa que para todos los $k != i,j$, debe haber al menos dos bordes de $x$ a $G_k$, y al menos dos bordes de $y$ a $G_k$. Por lo $G(j,k) \ge 4$ para todos los $k != i,j$.
Por eso, $G(i,j) \ge 4$ para todas las parejas, excepto un cierto conjunto $S$. Lo hemos demostrado anteriormente que si $(i,j) \in S$, entonces cualquiera de las $i$ o $j$ está impedido de ser, en cualquier otro par de $S$. Por lo $S$ puede tener en la mayoría de $\chi - 1$ pares. Así tenemos
$$
|E| \ge 2(\chi - 1) + 4(\frac{(\chi)(\chi-1)}{2} - (\chi - 1)) = 2(\chi-1)^2.
$$
Bonito problema!
