4
$\begingroup$

Theorem. Let $G = (V,E)$ be a simple graph with $n$ vertices, $m$ edges and $\chi (G) = k$. Then, $$m \geqslant {k \choose 2}$$

I tried proving myself but made little to no progress. I am aware of the inequality $$n/ \alpha (G) \leqslant \chi (G) \leqslant \Delta(G) + 1,$$ where $\Delta (G)$ is the maximum degree in $G$ and $\alpha (G)$ is the size of the maximum independent set of vertices in the graph. Does anybody have any tips? (tips are appreciated more than complete answers!)

$\endgroup$
2
$\begingroup$

Hint: If you have a hypothetical counter-example, can you show you have two colours which are not connected?

$\endgroup$
  • $\begingroup$ Yes. Suppose $m < {k \choose 2}$. Then take any set $S \subseteq V$ with $|S| = k$ all labeled different colors. This graph is not complete (due to assumption on $m$), so there is a pair $s_1,s_2 \in S$ that are different colors but not adjacent. But I do not see how this implies a contradiction/reduces the chromatic number? $\endgroup$ – user394255 Aug 11 '17 at 10:12
  • $\begingroup$ @Adrianos Can you see how to reduce the number of colours? You need colours not adjacent across the whole graph. $\endgroup$ – Mark Bennet Aug 11 '17 at 10:14
0
$\begingroup$

Color classes are necessarily pairwise connected by at least one edge (otherwise you could merge them), and since there are $k$ color classes ...

$\endgroup$

Your Answer

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