In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree 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 colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most colors, where is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964. Discovery The theorem discovered by Russian mathematician Vadim G. Vizing was published in 1964 when Vizing was working in Novosibirsk and became known as Vizing's theorem. Indian mathematician R. P. Gupta independently discovered the theorem, while undertaking his doctorate (1965-1967). Examples When , the graph must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with are of class one. When , the graph must be a disjoint union of paths and cycles. If all cycles are even, they can be 2-edge-colored by alternating the two colors around each cycle. However, if there exists at least one odd cycle, then no 2-edge-coloring is possible. That is, a graph with is of class one if and only if it is bipartite. Proof This proof is inspired by . Let be a simple undirected graph. We proceed by induction on , the number of edges. If the graph is empty, the theorem trivially holds. Let and suppose a proper -edge-coloring exists for all where . We say that color } is missing in with respect to proper -edge-coloring if for all . Also, let -path from denote the unique maximal path starting in with -colored edge and alternating the colors of edges (the second edge has color , the third edge has color and so on), its length can be . Note that if is a proper -edge-coloring of then every vertex has a missing color with respect to . Suppose that no proper -edge-coloring of exists. This is equivalent to this statement: (1) Let and be arbitrary proper -edge-coloring of and be missing from and be missing from with respect to . Then the -path from ends in . This is equivalent, because if