Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. This partitions graphs into two classes, with the ones requiring colors known as class 1, and the ones requiring colors known as 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 Conjecture## Explore with Wolfram|Alpha

## References

Misra, J. and Gries, D. "A Constructive Proof of Vizing's Theorem."*Inform. Process. Lett.*

**41**, 131-133, 1992.Royle, G. "Class 2 Graphs." 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 Theorem## Cite this as:

Weisstein, Eric W. "Vizing's Theorem."
From *MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/VizingsTheorem.html