Encyclopedia

Critical graph

Undirected graph

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated September 16, 2026

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. Each time a single edge or vertex (along with its incident edges) is removed from a critical graph, the decrease in the number of colors needed to color that graph cannot be by more than one.

01Variations

A $k$ -critical graph is a critical graph with chromatic number $k$ . A graph $G$ with chromatic number $k$ is $k$ -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 $k$ -critical graph $G$ with $n$ vertices and $m$ edges:

$G$ has only one component.
$G$ is finite (this is the De Bruijn-Erdős theorem).
The minimum degree $\delta (G)$ obeys the inequality $\delta (G)\geq k-1$ . That is, every vertex is adjacent to at least $k-1$ others. More strongly, $G$ is $(k-1)$ -edge-connected.
If $G$ is a regular graph with degree $k-1$ , meaning every vertex is adjacent to exactly $k-1$ others, then $G$ is either the complete graph $K_{k}$ with $n=k$ vertices, or an odd-length cycle graph. This is Brooks' theorem.
$2m\geq (k-1)n+k-3$ .
$2m\geq (k-1)n+(k-3)/(k^{2}-3)n$ .
Either $G$ 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 $G$ has at least $2k-1$ vertices. More strongly, either $G$ has a decomposition of this type, or for every vertex $v$ of $G$ there is a $k$ -coloring in which $v$ is the only vertex of its color and every other color class has at least two vertices.

Graph $G$ is vertex-critical if and only if for every vertex $v$ , there is an optimal proper coloring in which $v$ is a singleton color class.

As Hajós (1961) showed, every $k$ -critical graph may be formed from a complete graph $K_{k}$ by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require $k$ colors in any proper coloring.

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 $K_{k}$ is the only double-critical $k$ -chromatic graph.

Watch videos about Critical graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Critical graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Critical graph sample.svg by Claudio Rocchini, CC BY-SA 3.0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Critical graph

01Variations

Sources and credits

Related topics

Factor-critical graph