Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 3 / 17F / b / Solution

The Vizing theorem states that for every finite simple graph of maximum vertex degree $\Delta$, its edge chromatic number satisfies $\boxed{\Delta \le {\chi }^{\prime }(G)\le \Delta +1}$. The lower bound follows because all edges incident to a maximum-degree vertex need different colors. The simplicity hypothesis matters: unrestricted multigraphs need not satisfy this upper bound.