Prove that every $k$-chromatic graph has size $m\geq \binom k2 $

Question

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.

Answer 1

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}$

Answer 2

Suppose $G$ is $k$-chromatic. Consider a proper coloring of $G$ with $k$ colors; call the colors $1,\dots,k$. For each pair of colors $i,j$ ($1\le i\lt j\le k$) there must be at least one edge joining a vertex of color $i$ to a vertex of color $j$; for, if there were no such edge, then we could collapse colors $i$ and $j$ to a single color, and get a proper coloring of $G$ with only $k-1$ colors. Since there is at least one edge for each pair of distinct colors, the graph $G$ has at least $\binom k2$ edges.

Answer 3

I think you can also argue like this. $G$ is $k$-chromatic, so $G$ has a subgraph of complete $k$-partite. Since every vertices in the same partite has the same color, you can treat each partite as one vertex. This is a complete $k$-partite so every partite is connected to $k-1$ other partites. If you treat each partite as a vertex, then you will have $K_k$ which has exactly $\binom{k}{2}$ edges. Since every partite has at least 1 vertices so the number of edges in the $k$-partite is at least $\binom {k}{2}$ edges, thus $m_G \geq \binom{k}{2}$

Answer 4

This question was also answered here:

Prove, that graph $G$ has at least $\chi(G)(\chi(G)-1)/2$ edges.

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

Answer 5

Basically for a $k$ chromatic graph with $n$ vertices, there are $k$ edges such that all are adjacent to each other which mean every 2 vertices of those $k$ vertices are connected, i.e, there are at least $_kC_2$ (or $\binom k2$) edges in the graph.