Vizing's theorem states that the edge chromatic number of a finite simple graph is either 
or 
, where 
is its maximum vertex
degree (Misra and Gries 1992). The graphs requiring
colors are class
1 graphs, and those requiring 
colors are class 2 graphs.
Vizing's Theorem
See also
Brooks' Theorem, Class 1 Graph, Class 2 Graph, Degree Sequence, Edge Chromatic Number, Snark, Vertex Degree, Vizing ConjectureExplore with Wolfram|Alpha
References
Misra, J. and Gries, D. "A Constructive Proof of Vizing's Theorem." Inform. Process. Lett. 41, 131-133, 1992. https://doi.org/10.1016/0020-0190(92)90041-S.Royle, G. "Class 2 Graphs." https://web.archive.org/web/20130518153000/http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.Scheinerman, E. R. and Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, p. 77, 2011.Referenced on Wolfram|Alpha
Vizing's TheoremCite this as:
Weisstein, Eric W. "Vizing's Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VizingsTheorem.html