No he sido capaz de encontrar una prueba de que la declaración de que si un gráfico de Gχ(g)=k, entonces debe tener al menos \binom{k}{2} bordes. Te gustaría ser capaz de mostrar a una prueba simple?
Respuesta
¿Demasiados anuncios?Supongamos que tenemos un k-coloración de nuestro gráfico, con \chi(g)=k. A continuación, para cualquiera de los dos colores, llamada de rojo y azul, debe haber alguna arista que los une; si no existiera, podríamos pintar cada borde rojo y azul, y tendríamos un (k-1)-colorante de nuestro gráfico. Hay \binom{k}{2} pares de colores, y cualquier borde no se puede conectar más de 2 colores, por lo que debe haber, al menos, \binom{k}{2} bordes en nuestro gráfico.