Minimum number of edges in a graph of order n with chromatic number k

[math8]

What is the minimum number of edges in a k-chromatic connected graph of order n?

I have read somewhere that this number is equal to \left(\begin{array}{c} k \\2 \end{array} \right) +n -k

I was thinking about using K_k, the complete graph with k vertices. We know that the number of edges in K_k is equal to \left(\begin{array}{c} k \\2 \end{array} \right).

Also, I wanted to use the fact that if \chi (M) = k i.e. the chromatic number of a graph M is equal to k, and if a vertex v has degree strictly less than k, then the chromatic number of ( M together with v and its edges) is also equal to k.

I am not sure how start, I need help organizing my ideas.

 

[bpet]

Did you solve it?

One approach could be to prove Hadwiger's conjecture, then it would be an easy corollary.

HTH