Vizing’s Theorem – The Math


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$:

Screen%20Shot%202014-04-10%20at%205.49.41%20PM.png

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

Screen%20Shot%202014-04-10%20at%205.51.49%20PM.png

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.



The math online

Leave a Comment

Your email address will not be published. Required fields are marked *