Edge connectivity of a critical graph
Task number: 4062
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.
Solution
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.
