1
$\begingroup$

I have proved the statement : Every graph $G$ with $\chi(g)=k$ has at least $\binom{k}{2}$ edges. I did this my saying for any 2 colours, there exists an edge connecting one vertex of one colour to the other, otherwise you could set all vertices of one colour to be the first and then you would have a graph with a $k-1$ colouring. I said that there are $\binom{k}{2}$ possible permutations of pairs of colours, and since any edge cannot connect more than 2 colours, that means that there must be $\binom{k}{2}$ edges of the graph.

What I am struggling with is the next part: Let $e(G) = m$ be the number of edges in $G$, using the result proved above, prove that $\chi(g)\leq \frac{1}{2} + \sqrt{2m+\frac{1}{4}}$

I'm not really sure where to even start with this, I have tried to find the inverse of the top result, if given the number of edges what can that say about the chromatic number but haven't had any success in doing so. Is there any hints you could give me or show me how to get started with this proof? Thanks.

$\endgroup$
1
$\begingroup$

You have done the hardest part already. The rest is algebraic manipulations of the result you have proved.

\begin{align} &m \ge \binom{k}{2} = \frac{k(k-1)}{2}\\ \Rightarrow \quad &2m \ge k^2 -k \\ \Rightarrow \quad &2m +\frac{1}{4} \ge k^2 -k +\frac{1}{4}\\ \Rightarrow \quad &2m +\frac{1}{4} \ge (k-\frac{1}{2})^2 \\ \Rightarrow \quad & \frac{1}{2}+\sqrt{2m +\frac{1}{4}} \ge k \end{align}

$\endgroup$
  • $\begingroup$ Brilliant thank you! Must have been very tired yesterday to miss that! $\endgroup$ – Tim Hodgkin Feb 2 '16 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.