Critical graphs with connected complements

We show that given any vertex x of a k-colour-critical graph G with a connected complement, the graph G−x can be (k−1)-coloured so that every colour class contains at least 2 vertices. This extends the well-known theorem of Gallai, that a k-colour-critical graph with a connected complement has at least 2k−1 vertices. Our proof does not use matching theory. It is considerably shorter, conceptually simpler and more general than Gallaiʹs original proof.