## Edge connectivity of a critical graph

Let $$G$$ be a graph with the chromatic number $$k$$, such that each its proper subgraph has a chromatic number of at most $$k-1$$. Show that $$G$$ is necessarily edge $$( k-1)$$-connected.
By a contradiction. If $$G$$ was not edge $$(k-1)$$-connected, it would have an edge cut of size at most $$k-2$$ separating two components $$C$$ and $$C’$$. We color both with $$k-1$$ colors.
By merging the coloring, it may happen that some edge of the cut has both ends of the same color $$b$$. Because there are fewer cut edges than colors, we can find a color $$c$$ in the component $$C$$ such that no vertex of this color is incident with any edge of the cut. If we swap on $$C$$ the colors $$b$$ and $$c$$, we do not damage the coloring of the component $$C$$, but we reduce the number of the cut edges with ends of the same color.
We repeat this process until we get a coloring of the graph $$G$$ using at most $$k-1$$ colors, which is the desired contradiction.