# 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.

### Related post:

- Reisch receives SUNY Chancellor’s Award | News, Sports, Jobs – Evening Observer
- An overall 2nd place for Malta in an International Mental Mathematics Challenge – Malta Independent Online
- DU Admissions 2019: Mathematics Must In Best Of Four Subjects For Admission Into Eco(H); JMC, Stephen’s Stick To Old Rule – Swarajya
- Agami Education Foundation holds teachers’ training on Teaching Mathematics by Olympiad Technique – Dhaka Tribune
- 2nd place for Malta in international Mental Mathematics Challenge – Newsbook
- Darlington pupils among most-skilled mathematics in the UK – Darlington and Stockton Times
- Women and minority faculty in science, technology, engineering and mathematics (STEM) – Open Access Government
- The messy mathematics of British Columbia’s CleanBC plan – Business in Vancouver
- All Limerick student’s hard work adds up to him winning top mathematics award in Ireland – Limerick Leader
- CMU-Q researchers explore the mathematics of personalised medicine – The Peninsula Qatar