5
$\begingroup$

Can anybody give me any hints about how to prove that for any graph $G$ the number of edges in it is at least $\chi(G)(\chi(G)-1)/2$? $\chi(G)$ is the minimal number of colors we need to use to color the graph (it's chromatic index in other words).

I tried induction but I'm stuck at an induction step.

I do the induction on the number of edges.

When $|E(G)|=0$ then obviously we can color the graph using only one color, so the theorem holds.

Now induction step from $n \Rightarrow n+1$ edges.

Let's erase any edge $e=\{v,u\}$ from $G$. Then $\chi(G-e)$ is either the same, or $\chi(G-e)<\chi(G)$, because we relaxed the graph an $v$ and $u$ no longer need to have different colors. From the first case the thesis is clear, because $G-e$ has more then $\chi(G)(\chi(G)-1)/2$ edges so with the one we erased it's still more. But from the second case we only know that $G \geq \chi'(G)(\chi'(G)-1)/2$ and $\chi'(G)(\chi'(G)-1)/2 \leq \chi(G)(\chi(G)-1)/2$ so that gives me nothing...

$\endgroup$
10
$\begingroup$

Given a coloring of $G$ with $\chi(G)$ colors, there must be an edge between every two color classes, because otherwise we could color them the same color.

$\endgroup$
  • $\begingroup$ Thank you :) Incredibly simple and sweet answer :) Looks like my long inductive proof was not a wise choice :P $\endgroup$ – Arek Krawczyk Jan 20 '14 at 19:49

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.