Vizing's theorem

The set of Vizing is a 1964 published by Vadim G. Vizing mathematical theorem from graph theory. It provides both a lower limit and an upper limit for the chromatic index of a graph.

Let G be a multigraph, that is, a graph with multiple edges but no loops, with the chromatic index and the maximum degree. Furthermore denote h, the maximum number of edges which connect two vertices. Then the following inequality holds:

In the case of a simple graph, that is, of a graph without multiple edges, the above inequality then simplifies to: