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.
Thanks a lot in advance!
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.
Thanks a lot in advance!
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.