Return to Revisions

Your guess is correct. Denote $\chi(G)=k$. Then $G$ contains a subgraph with all degrees at least $k$ (proof: if degree of vertex $v$ is less than $k$, then $\chi(G\setminus v)=k$. Indeed, if $\chi(G\setminus v)<k$, color $G\setminus v$ with $k-1$ colors and then extend this coloring to $v$. So, minimal subgraph of $G$ with chromatic number $k$ can not have vertices of degree less than $k$.) Clearly it has at least $k+1$ vertices, thus at least $k(k+1)/2$ edges.