Demostrar que todo gráfico kkk-cromático tiene tamaño m≥(k2)m≥(k2)m\geq \binom k2

Sea G un$k$gráfico cromático de orden$n$y tamaño$m$. Que se le dé un color de$G$usando$k$colores. Denote las clases de color de G por$C_1,C_2,...C_k$. Vamos a ejecutar la vieja prueba por contradicción aquí. No estoy seguro si es necesario, pero lo que sea, me gusta. Entonces, asumimos que$m<\binom{k}{2}$Ahora, ¿esto ya no parece extraño?$G$tiene menos bordes que$K_k$? Obtenemos nuestra contradicción de esta última curiosidad. Considere el gráfico$H$, formado por la asociación de cada clase de color,$C_i$, con un vértice,$u_i$dónde$\; 1\le i\le k$y$u_iu_j\in E(H), i\ne j,$si y solo si$\exists$una arista entre cualquier vértice en$C_i$y cualquier vértice en$C_j$. Desde$|E(G)|=m<\binom{k}{2}$y desde$H$necesariamente tiene menos aristas que$G$, resulta que$H$no es un gráfico completo. Por lo tanto, existen 2 clases de color,$C_m$y$C_n$ $(m\ne n),$sin borde entre ellos. Cambiar el color de todos los vértices en$C_m$al color de los vértices en$C_n$. Esto produce una coloración de$G$con$k-1$colores, una contradicción. Por lo tanto, debe darse el caso de que$m\ge \binom{k}{2}$

Suponer$G$es$k$-cromático. Considere una coloración apropiada de$G$con$k$colores; llamar a los colores$1,\dots,k$. Para cada par de colores$i,j$($1\le i\lt j\le k$) debe haber al menos una arista uniendo un vértice de color$i$a un vértice de color$j$; porque, si no hubiera tal borde, entonces podríamos colapsar los colores$i$y$j$a un solo color, y obtener una coloración adecuada de$G$con solo$k-1$colores. Como hay al menos una arista para cada par de colores distintos, el gráfico$G$tiene al menos$\binom k2$bordes

Creo que también se puede argumentar así.$G$es$k$-cromático, entonces$G$tiene un subgrafo de completo$k$-partido Dado que todos los vértices en la misma partición tienen el mismo color, puede tratar cada partición como un vértice. Este es un completo$k$-partite por lo que cada partición está conectada a$k-1$otras partitas. Si tratas cada partición como un vértice, entonces tendrás$K_k$que tiene exactamente$\binom{k}{2}$bordes Dado que cada partición tiene al menos 1 vértices, el número de aristas en el$k$-partido es al menos$\binom {k}{2}$bordes, por lo tanto$m_G \geq \binom{k}{2}$

Esta pregunta también fue respondida aquí:

Demostrar, ese gráfico$G$tiene al menos$\chi(G)(\chi(G)-1)/2$bordes

desde$\binom{k}{2} = k(k-1)/2$

Básicamente para un$k$gráfico cromático con$n$vértices, hay$k$bordes tales que todos son adyacentes entre sí, lo que significa cada 2 vértices de esos$k$los vértices están conectados, es decir, hay al menos$_kC_2$(o$\binom k2$) aristas en el gráfico.