Vizing's Theorem

Theorem 1 (Vizing's Theorem): For any (simple) graph $G$ where $\chi ' (G)$ is the smallest integer $k$ for a good edge $k$-colouring and $\Delta (G)$ is the maximum degree in $G$, then $\Delta (G) \leq \chi ' (G) \leq \Delta (G) + 1$.

We will not prove this theorem, however this tells us that for any simple graph $G$, the chromatic index $\chi ' (G) = \Delta (G)$ or $\chi ' (G) = \Delta (G) + 1$. This makes finding the chromatic index a lot simpler for large graphs.

For example, the following simple graph $G$ has $\Delta (G) = 5$:

We note that we can obtain a good edge $5$-colouring as follows:

Hence $\chi ' (G) = 5$. If we couldn't obtain a good edge $5$-colouring, then Vizing's theorem says we could have obtained a good edge $6$-colouring.