# Criticality of a graph

What's the usual method for proving the criticality of a graph?

I've been trying out different methods and theorems but I can't find a decent method that's really convincing.

-
Wondering what a critical graph is? Wikipedia tells us that a graph is critical if removing any vertex or edge results in the chromatic number decreasing (by one). –  Yuval Filmus Feb 13 '11 at 22:56
A graph is critical if every one of its proper subgraphs (subgraph not equal to the original) has a chromatic color less than the original. –  K-RAN Feb 13 '11 at 23:10

If $G$ is $n$-critical (i.e. $\chi(G) = n$), then $\delta(G) \geq n-1$. So if $\delta(G) < n-1$ then $G$ is not $n$-critical.

-
I'm going to assume that delta is the degree of any vertex? And is this an actual theorem? –  K-RAN Feb 14 '11 at 1:27
If $G$ is $n$-critical then it is the complete graph. –  Yuval Filmus Feb 14 '11 at 2:28
Yuval- the 5-cycle is 3-critical (deleting any vertex gives a bipartite graph), but it is not the complete graph. –  Daniel Moskovich Nov 28 '11 at 14:16