Para el texto normal:

Question

Que $G$ sea un gráfico conectado que es $k$-regular y es un grafo completo ni un ciclo impar. Entonces el número cromático de $G$ es $k$. ¿Es cierto?

Answer 1

No, esto no es cierto. Por ejemplo, la utilidad gráfica de $K_{3,3}$ es cúbico, es decir, 3-regular. Sin embargo, también es bipartito. Es bien conocido que un gráfico es de 2 engañosa si y sólo si es bipartito. Así que tenemos un contraejemplo.