|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.
- Jamaican students to participate in OECD survey – Jamaica Observer
- Women who don’t know how to cook don’t know mathematics – MP – GhanaWeb
- UC Irvine algorithm solves Rubik’s Cube in just 1 second – University of California
- Scientists create Ramanujan Machine: what’s it for, why name it after him? – The Indian Express
- Migrant students immersed in engineering – Foothills Sun Gazette
- How bad is the gender diversity crisis in AI research? Study analysing 1.5million arxiv papers says it’s “serious” – Packt Hub
- For the perfect martini, thank fluid mechanics – The Science Show – ABC News
- A mathematics whizz – Midrand Reporter
- Shakuntala Devi: Numero Uno in Math Wizardry – Hindustan Times
- US-settled siblings keen to teach Madurai students math for free – Times of India