Vizing's theorem

Remarks

The lower bound is clear: the $\Delta$ edges at a vertex of maximum degree need distinct colours. The upper bound is proved by colouring the edges one at a time with $\Delta + 1$ colours. When a new edge cannot be coloured, a fan of edges at one end and a path in two colours are recoloured to free a colour. Graphs with $\chi' = \Delta$ are of class 1, and graphs with $\chi' = \Delta + 1$ are of class 2. An odd cycle has $\Delta = 2$ and needs $3$ colours, so it is of class 2; every bipartite graph is of class 1, by a theorem of Kőnig. The hypothesis that $G$ is simple is needed: the multigraph on three vertices with each pair joined by $k$ parallel edges has $\Delta = 2k$ but needs $3k$ colours. Deciding whether a graph is of class 1 is NP-complete.

Going deeper

For a student

For vertex colouring, the chromatic number can be far above any simple lower bound, but for edge colouring Vizing's theorem pins the answer to two values. The proof is constructive and gives an efficient algorithm for a colouring with $\Delta + 1$ colours. For multigraphs, Vizing also proved $\chi' \le \Delta + \mu$, where $\mu$ is the largest number of parallel edges.