Prove that every $k$-chromatic graph has size $m\geq \binom k2$.
Here is what I know:
Let $G$ be a $k$-chromatic graph, that mean $\chi(G)=k$. Thus $G$ must have a subgraph of a complete $k$-partite graph, say $H$. Hence $m_G \geq m_H$.
Here are my questions
1) I'm kinda confused between $k$-coloring, $k$-colorable and $k$-chromatic.
I know that $G$ is $k$-colorable means $\chi (G) \leq k$ and $\chi(G)$ is the minimum number of colors needed for a legal coloring of $G$. Then the book said if $G$ is $k$-chromatic then there exists a $k$-coloring but no $(k-1)$-coloring.
I feel like the book is just kicking me around.
2) I know $\binom k2$ is the size of a complete graph of order $k$, but I can't see how a $k$-partite graph has that size.
Best Answer
Let G be a $k$ chromatic graph of order $n$ and size $m$. Let there be given a coloring of $G$ using $k$ colors. Denote the color classes of G by $C_1,C_2,...C_k$. We're gonna run the ol' proof by contradiction here. I'm not sure if it's necessary, but whatever, I like it. So, we assume that $m<\binom{k}{2}$ Now, doesn't this already seem weird? $G$ has less edges than $K_k$? We get our contradiction from this last curiosity. Consider the graph $H$, formed by associating each color class, $C_i$, with a vertex, $u_i$ where$\; 1\le i\le k$ and $u_iu_j\in E(H), i\ne j, $ if and only if $\exists$ an edge between any vertex in $C_i$ and any vertex in $C_j$. Since $|E(G)|=m<\binom{k}{2}$ and since $H$ necessarily has less edges than $G$, it follows that $H$ is not a complete graph. Therefore, there exists 2 color classes, $C_m$ and $C_n$ $(m\ne n),$ with no edge between them. Change the color of all vertices in $C_m$ to the color of the vertices in $C_n$. This produces a coloring of $G$ with $k-1$ colors, a contradiction. Therefore, it must be the case that $m\ge \binom{k}{2}$