8
$\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$

1 Answer 1

Reset to default
13
$\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$
1
  • $\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, 2014 at 19:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .