Probablemente, la siguiente no sea la forma más elegante, pero aquí está de todos modos. Ten en cuenta que hay algunos detalles que dejo para que los completes tú. Por supuesto, siempre que digo "colorear", me refiero a una coloración adecuada.
Para un gráfico $G$ , dejemos que $\Delta(G)$ denota el grado máximo entre todos los vértices de $G$ . Recordemos el siguiente resultado famoso.
Teorema de Brook : Dejemos que $G$ sea un gráfico conectado. Si $G$ es un ciclo de longitud impar o un gráfico completo, entonces $\chi(G)=\Delta(G)+1$ . Por lo demás, $\chi(G)\leq \Delta(G)$ .
A continuación, convénzase de lo siguiente.
Lema : Si $H$ es un gráfico sin triángulos en $5$ o menos vértices, entonces $H$ es un ciclo de longitud $5$ o $\chi(H)\leq 2$ .
Supongamos ahora que nos dan un gráfico sin triángulos $G$ en $10$ o menos vértices. También podemos suponer que $G$ está conectado y tiene al menos $6$ vértices. Además, podemos suponer que $\Delta(G)\geq 4$ .
Dejemos que $v$ sea un vértice de grado $\Delta(G)$ , dejemos que $A$ sean los vecinos de $v$ . Tenga en cuenta que $A$ es un conjunto independiente (es decir, no existen aristas entre los vértices de $A$ ). Sea $B$ sea el subgrafo inducido por los no vecinos de $v$ .
Si $\Delta(G)>4$ entonces $B$ tiene como máximo $4$ vértices. Por el lema, los vértices de $B$ se puede colorear con dos colores, por ejemplo, rojo y azul. A continuación, podemos colorear todos los vértices de $A$ verde. Por último, dado que $v$ no es adyacente a ningún vértice de $B$ podemos colorearlo de rojo. Así hemos encontrado un $3$ -coloración de $G$ .
Si $\Delta(G)=4$ y $B$ es pas un ciclo de duración $5$ , entonces se procede como en el párrafo anterior para obtener un $3$ -coloración de $G$ . Por lo tanto, ahora podemos suponer que $\Delta(G)=4$ y que $B$ es un ciclo de longitud $5$ . Tenga en cuenta que esto significa $G$ tiene $10$ vértices. En particular, ahora sabemos que cualquier grafo sin triángulos en a lo sumo $9$ vértices es $3$ -Colable.
Ahora, si cualquier vértice $w$ en $G$ tiene $\deg(w)\leq 2$ y lo borrará. El gráfico resultante $G-w$ tiene $9$ vértices y por tanto podemos colorearlo con tres colores. Pero como el vértice eliminado tiene como máximo dos vecinos en $G$ esto significa que tal coloración de $G-w$ puede extenderse a una coloración de $G$ usando tres colores, y ya está. Así que ahora supongamos que todos los vértices en $G$ tener un título al menos $3$ . Desde $G$ es libre de triángulos, lo que significa que cada vértice de $A$ tiene exactamente dos vecinos en $B$ . Así que en este punto, $G$ parece:
![enter image description here]()
Supongamos que un vértice en $b\in B$ es adyacente a los cuatro vecinos en $A$ . Como no hay vértices de grado $2$ los dos vecinos de $b$ también son adyacentes a un vértice en $A$ . Pero entonces $G$ no estaría libre de triángulos, por lo que ningún vértice de $B$ puede ser adyacente a los cuatro vértices de $A$ .
Supongamos que un vértice $b\in B$ tiene exactamente tres vecinos en $A$ . Esto obliga a los dos vecinos de $b$ en $B$ para ser adyacente al cuarto vértice en $A$ y los vecinos de $b$ en $A$ sea adyacente a uno de los dos no vecinos de $b$ en $B$ . En mil palabras, $G$ parece:
![enter image description here]()
Pero ahora podemos $3$ -color $G$ como tal:
![enter image description here]()
Por último, podemos suponer que ningún vértice de $B$ tiene más de dos vecinos en $A$ . Pero como hay $8$ bordes entre $A$ y $B$ esto significa que exactamente tres vértices en $B$ tienen dos vecinos en $A$ . Por lo tanto, dos de estos vértices deben ser adyacentes, por lo que el gráfico se ve así:
![enter image description here]()
Colorea los vértices así:
![enter image description here]()
Pero como $G$ es libre de triángulos, esto es en realidad un $3$ -Coloración.
