What is the minimum number of edges in a [itex]k[/itex]-chromatic connected graph of order [itex]n[/itex]?(adsbygoogle = window.adsbygoogle || []).push({});

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

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

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

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

**Physics Forums | Science Articles, Homework Help, Discussion**