Is there any relation between average degree of a graph and chromatic number?
Like if an average degree for a graph is 3.4. Can we say that the graph is not 2-colorable?
for Number of edges = 17 and vertices are 10.
So my question is can we do prove of this using handshaking lemma min.degree <= 2E/V <= max. degree ?
i.e. if my average degree comes say x then chromatic number is greater than or equal to x ?
Best Answer
You can't do very much. Note that the complete bipartite graph $K_{n,n}$ has average degree $n$ yet it is 2-colorable.
I think the "best" bound of this type that one could possibly obtain is by using the inequality $$\chi(G) \leq \frac{1}{2} + \sqrt{2m+\frac{1}{4}},$$ holding for a graph with $m$ edges.