# Minimum number of edges in a graph of order n

• Oct 12th 2011, 03:27 PM
math8
Minimum number of edges in a graph of order n
What is the minimum number of edges in a $\displaystyle k$-chromatic connected graph of order $\displaystyle n$?

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

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

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

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