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?
0
$\begingroup$
graph-theory
-
5Deleting and re-asking questions is not appropriate behavior on this site. I have merged your duplicate questions. – 2012-07-06