Editing Critical graph (section)

== Variations ==
A ''<math>k</math>-critical graph'' is a critical graph with chromatic number <math>k</math>. A graph <math>G</math> with chromatic number <math>k</math> is ''<math>k</math>-vertex-critical'' if each of its vertices is a critical element. Critical graphs are the ''minimal'' members in terms of chromatic number, which is a very important measure in graph theory.

Some properties of a <math>k</math>-critical graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges:
* <math>G</math> has only one [[Glossary of graph theory|component]].  
* <math>G</math> is finite (this is the [[de Bruijn–Erdős theorem (graph theory)|De Bruijn–Erdős theorem]]).{{r|dbe}}
* The minimum [[degree (graph theory)|degree]] <math>\delta(G)</math> obeys the inequality <math>\delta(G)\ge k-1</math>. That is, every vertex is adjacent to at least <math>k-1</math> others. More strongly, <math>G</math> is <math>(k-1)</math>-[[K-edge-connected graph|edge-connected]].{{r|lovasz}}
* If <math>G</math> is a [[regular graph]] with degree <math>k-1</math>, meaning every vertex is adjacent to exactly <math>k-1</math> others, then <math>G</math> is either the [[complete graph]] <math>K_k</math> with <math>n=k</math> vertices, or an odd-length [[cycle graph]]. This is [[Brooks' theorem]].{{r|brooks}}
* <math>2m\ge(k-1)n+k-3</math>.{{r|dirac}}
* <math>2m\ge (k-1)n+\lfloor(k-3)/(k^2-3)\rfloor n</math>.{{r|gallai-1}}
* Either <math>G</math> may be decomposed into two smaller critical graphs, with an edge between every pair of vertices that includes one vertex from each of the two subgraphs, or <math>G</math> has at least <math>2k-1</math> vertices.{{r|gallai-2}} More strongly, either <math>G</math> has a decomposition of this type, or for every vertex <math>v</math> of <math>G</math> there is a <math>k</math>-coloring in which <math>v</math> is the only vertex of its color and every other color class has at least two vertices.{{r|stehlik}}

Graph <math>G</math> is vertex-critical [[if and only if]] for every vertex <math>v</math>, there is an optimal proper coloring in which <math>v</math> is a singleton color class.

As {{harvtxt|Hajós|1961}} showed, every <math>k</math>-critical graph may be formed from a [[complete graph]] <math>K_k</math> by combining the [[Hajós construction]] with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require <math>k</math> colors in any proper coloring.{{r|hajos}}

A '''double-critical graph''' is a connected graph in which the deletion of any pair of adjacent vertices decreases the chromatic number by two. It is an [[open problem]] to determine whether <math>K_k</math> is the only double-critical <math>k</math>-chromatic graph.{{r|erdos}}