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?
Critical graph inequality - proof?
-
5Deleting and re-asking questions is not appropriate behavior on this site. I have merged your duplicate questions. – 2012-07-06
1 Answers
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.