Demuestra que existen dos conjuntos con aristas de colores únicos en un grafo completo coloreado

Question

Dejemos que $G$ sea un grafo completo con aristas de color azul o rojo. Entre las aristas de cada $4$ vértices, existe un triángulo con sólo aristas azules/rojas. Demostrar que existe una descomposición de los vértices en dos partes ( $S$ y $T$ ) para que las aristas en parte $T$ son azules y los bordes en parte $S$ son de color rojo. Tenga en cuenta que $S$ o $T$ podría estar vacía y sin ningún vértice.

El problema anterior puede convertirse fácilmente en el siguiente: Sea $G$ sea un gráfico. Supongamos que $X$ es un conjunto de $4$ vértices en $G$ . Existe un ciclo de tamaño $3$ ya sea en $X$ o Complemento de $X$ . Demostrar que los vértices de $G$ puede descomponerse en una camarilla y un conjunto independiente.

Gracias de antemano por su ayuda.

Answer 1

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.