Exercise 2136Combinatorics › Graph theoryM1Added 3 Nov 2026

Edge coloring (Vizing)

#Vizing#edge coloring#chromatic index

Statement

State Vizing's theorem on edge coloring.

Hint

For a simple graph with maximum degree $\Delta$ , the edge chromatic number is $\Delta$ or $\Delta+1$ .

Show solutionHide solution

Theorem. The edge chromatic number $\chi'(G)$ of a simple graph satisfies $\Delta\le\chi'(G)\le\Delta+1$ .

Classification. Graphs with $\chi'=\Delta$ are "class 1"; those with $\chi'=\Delta+1$ are "class 2".

Bipartite. $\chi'=\Delta$ (Kőnig). Cubics of class 2 include the Petersen graph.

Conclusion. Vizing's theorem limits edge chromatic numbers to two possible values.