Editing Edge coloring (section)

===Vizing's theorem===
{{Main|Vizing's theorem}}
The edge chromatic number of a graph {{mvar|G}} is very closely related to the [[Degree (graph theory)|maximum degree]] {{math|Δ(''G'')}}, the largest number of edges incident to any single vertex of {{mvar|G}}. Clearly, {{math|χ&prime;(''G'') ≥ Δ(''G'')}}, for if {{math|Δ}} different edges all meet at the same vertex {{mvar|v}}, then all of these edges need to be assigned different colors from each other, and that can only be possible if there are at least {{math|Δ}} colors available to be assigned. [[Vizing's theorem]] (named for [[Vadim G. Vizing]] who published it in 1964) states that this bound is almost tight: for any graph, the edge chromatic number is either {{math|Δ(''G'')}} or {{math|Δ(''G'') + 1}}.
When {{math|1=χ&prime;(''G'') = Δ(''G'')}}, ''G'' is said to be of class 1; otherwise, it is said to be of class 2.

Every bipartite graph is of class 1,<ref>{{harvtxt|Kőnig|1916}}</ref> and [[almost all]] [[random graph]]s are of class 1.<ref>{{harvtxt|Erdős|Wilson|1977}}.</ref> However, it is [[NP-complete]] to determine whether an arbitrary graph is of class 1.<ref>{{harvtxt|Holyer|1981}}.</ref>

{{harvtxt|Vizing|1965}} proved that [[planar graph]]s of maximum degree at least eight are of class one and conjectured that the same is true for planar graphs of maximum degree seven or six. On the other hand, there exist planar graphs of maximum degree ranging from two through five that are of class two. The conjecture has since been proven for graphs of maximum degree seven.<ref>{{harvtxt|Sanders|Zhao|2001}}.</ref> [[Bridge (graph theory)|Bridgeless]] planar [[cubic graph]]s are all of class 1; this is an equivalent form of the [[four color theorem]].<ref>{{harvtxt|Tait|1880}}; {{harvtxt|Appel|Haken|1976}}.</ref>