- #1
math8
- 160
- 0
What is the minimum number of edges in a [itex]k[/itex]-chromatic connected graph of order [itex]n[/itex]?
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.
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.