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

- Grade Nine learners taught mathematics skills – Tembisan
- A Library Browse Leads Math’s Bill Dunham to Question the Origins of The Möbius Function – Bryn Mawr Now
- Year 5 and 6 students to sit competition this Wednesday – Great Lakes Advocate
- USC student wins silver medal in China math contest – SunStar Philippines
- CBSE Exam 2020: Two separate examinations to be conducted for Class 10 Mathematics – Jagran Josh
- Concepts incomplete, problems unsolvable in math textbooks – Times of India
- Education Ministry to Host Tertiary and Employment Fairs – Government of Jamaica, Jamaica Information Service
- Vogue’s Edwina McCann and Westpac’s Anastasia Cammaroto on how they inspire women to pursue STEM – Vogue Australia
- Jonee Wilson, Temple Walkowiak to Measure High-Quality Instructional Practices to Support Marginalized Students in Rigorous Mathematics through NSF Grant – NC State College of Education
- Australian Conference on Science and Mathematics Education – Australian Academy of Science