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

1. Oct 12, 2011

### 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.

2. Oct 22, 2011

### bpet

Did you solve it?

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

HTH