Loading [MathJax]/extensions/TeX/mathchoice.js

8 votos

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

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?

19voto

Don L. Puntos 316

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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X