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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
R. C. Read (via MathSciNet) asserts that this paper:
contains an early proof of the claim. Quote from the review:
Improvements of Gallai's result are claimed to be in: