Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Vizing's theorem
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, Vizing's theorem states that every simple <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> may be <a href="/facts/Edge_coloring/AcdpUxCv">edge colored</a> using a number of colors that is at most one larger than the maximum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> Δ of the graph. At least Δ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Δ colors suffice, and "class two" graphs for which Δ + 1 colors are necessary. A more general version of Vizing's theorem states that every undirected <a href="/facts/Multigraph/udmS0Cp0">multigraph</a> without loops can be colored with at most Δ+µ colors, where µ is the <a href="/facts/Glossary_of_graph_theory_terms/W0MqKkyE">multiplicity</a> of the multigraph. The theorem is named for <a href="/facts/Vadim_G._Vizing/oHwYWIsH">Vadim G. Vizing</a> who published it in 1964. </p>