Vizing's theorem

Every finite simple graph can have its edges colored with at most Δ + 1 colors so that adjacent edges receive different colors, where Δ is its maximum degree.

Edge coloring: An assignment of colors to graph edges in which edges sharing a vertex receive different colors. Vizing’s theorem bounds the number of colors needed for this graph-coloring problem.
Class 1 graph: A graph whose edge chromatic number equals its maximum degree. These graphs attain the lower bound in Vizing’s theorem.
Vadim Vizing: A Russian mathematician known for foundational results in graph coloring and combinatorial optimization. He proved the theorem for simple graphs in 1964.
Complete graph: A simple graph in which every pair of distinct vertices is joined by an edge. Complete graphs provide familiar examples whose edge chromatic number can be computed exactly.
Maximum degree: The largest number of edges incident to any one vertex in a graph. It supplies Δ, the lower bound and central parameter in Vizing’s bound.
Class 2 graph: A graph whose edge chromatic number is one greater than its maximum degree. These graphs attain the theorem’s upper bound instead of the degree lower bound.
Shannon's theorem: A bound stating that a multigraph’s edge chromatic number is at most ⌊3Δ/2⌋. It addresses edge coloring with parallel edges, where Vizing’s simple-graph bound does not apply.
Odd cycle: A cycle containing an odd number of edges. Its maximum degree is two, but its edges require three colors, attaining the upper bound.
Fan (graph theory): A sequence of edges incident to one vertex, arranged so colors can be shifted during an edge-coloring argument. Vizing’s proof builds a fan to expose a missing color at a neighboring vertex.
Edge chromatic number: The minimum number of colors required for a proper edge coloring of a graph. Vizing’s theorem places this number in the two-value interval Δ through Δ + 1.

Linked from 5 pages