Cromática Número De Identidad Que Involucra Los Bordes

Question

Estoy tratando de demostrar que la siguiente:

Deje $G$ ser un simple gráfico con $m$ bordes. Mostrar que $\chi(G)\leq \frac{1}{2}+\sqrt{2m+\frac{1}{4}}.$

Un minuto muy poco de manipulación algebraica que muestra que esto es equivalente a probar $$\chi(G)(\chi(G)-1)\leq 2m.$$ a partir De aquí, estoy un poco atascado. Podría alguien sugerir una dirección a la cabeza?

Por favor, no hay soluciones, sólo sugerencias.

Answer 1

SUGERENCIA: UN poco más de la manipulación convierte en $$m\ge\binom{\chi(G)}2\;,$$, que puede ser entendido como diciendo que debe haber al menos tantas aristas como hay pares de colores en un mínimo de colorear.

Answer 2

El hecho de que $G$ ha cromática número $\chi(G)$ significa que usted puede partición de los vértices de la gráfica en $\chi(G)$ clases disjuntas tal que los vértices en la misma clase, sin vecinos.

Se puede contar el número de aristas con respecto a dicha partición?