0
$\begingroup$

I am curious to see a rigorous proof of the following inequality; if $G$ is a $k$-critical graph, then $k(|V(G)|-1)\le2|E(G)|.$ Does anyone know if it is a well known inequality? If so what inequality is it and how is it relevant?

  • 5
    Deleting and re-asking questions is not appropriate behavior on this site. I have merged your duplicate questions.2012-07-06

1 Answers 1

1

R. C. Read (via MathSciNet) asserts that this paper:

Gallai, T., Kritische Graphen. I., Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 1963 165–192.

contains an early proof of the claim. Quote from the review:

Another consequence of (1) is a lower bound for the number of edges in a k-critical graph with n points. It is shown that the number of edges is not less than $\frac{1}{2}n(k−1)+n/(2k+18)$.

Improvements of Gallai's result are claimed to be in:

Krivelevich, Michael, On the minimal number of edges in color-critical graphs. Combinatorica 17 (1997), no. 3, 401–426.

Krivelevich, Michael, An improved bound on the minimal number of edges in color-critical graphs. Electron. J. Combin. 5 (1998), Research Paper 4, 4 pp.

Kostochka, Alexandr V., Stiebitz, Michael, A new lower bound on the number of edges in colour-critical graphs and hypergraphs. J. Combin. Theory Ser. B 87 (2003), no. 2, 374–402.