los bordes cromática y de número de la desigualdad

Question

No he sido capaz de encontrar una prueba de que la declaración de que si un gráfico de $G$$\chi(g)=k$, entonces debe tener al menos $\binom{k}{2}$ bordes. Te gustaría ser capaz de mostrar a una prueba simple?

Answer 1

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.