Por una "camarilla roja" me refiero a un conjunto de vértices tales que todas las aristas entre ellos son rojas. Sea $S$ sea una camarilla roja del máximo tamaño posible, y sea $T$ sea el complemento de $S$ . Afirmo que todas las aristas que unen dos vértices en $T$ son azules.
Supongamos por contradicción que hay dos vértices $v,w\in T$ tal que la arista $vw$ es de color rojo. Cada uno de esos vértices está unido por una arista azul a al menos un vértice de $S$ Si no, podríamos añadirlo a $S$ y conseguir una camarilla roja más grande.
Primero, supongamos que podemos encontrar dos vértices distintos $x,y\in S$ tal que $vx$ y $wy$ son azules. Entonces $xy$ es rojo, y el conjunto $v,w,x,y$ no contiene ningún triángulo con todas sus aristas del mismo color.
No podemos encontrar dos vértices distintos $x,y\in S$ como en el caso anterior, entonces sólo hay un vértice en $S$ Llámalo $x$ que se une a $v$ por un borde azul, y el mismo $x$ es el único vértice en $S$ unido a $w$ por un borde azul. Pero entonces $(S\setminus\{x\})\cup\{v,w\}$ es una camarilla roja que contiene un vértice más que $S$ una contradicción.
Observación. Este ejercicio dice que un gráfico, que no contiene $P_4$ o $C_4$ o $\overline{C_4}$ (el complemento de $C_4$ ) como subgrafo inducido, es un gráfico de división . Esta condición suficiente para un gráfico dividido no es ciertamente necesaria, ya que $P_4$ es un gráfico dividido. De hecho, un gráfico es un gráfico dividido si y sólo si no contiene $C_5$ o $C_4$ o $\overline{C_4}$ como un subgrafo inducido, pero demostrarlo sería un ejercicio más difícil.
