Alexandr Kostochka found the following new proof to the classical theorem.
Vizing’s Theorem. For every simple graph , .
Proof. We prove by contradiction; assume that is a minimal counter-example (in terms of number of edges) to the statement; that is, has no edge-()-coloring.
Let be an edge-()-coloring of . For every , let denote the set of colors in not used to color the edges incident to ; one can see that .
Construct the auxiliary multidigraph as follows: and there is a directed edge from to in if . Intuitively an edge from to means that if we can recolor , then we can recolor as well. Let be the set of vertices reachable in from ( as well); any recoloring of an edge for will imply that we can color . Since the out-neighbors of a vertex reachable from also are reachable from , for every . Therefore
and the theorem will be proven if we can show that
- for all ;
a contradiction. Items (1) and (2) follow from the following claims. Let .
Claim 1 (Exchange argument). for every .
Proof sketch. Recolor the edges of the form for each on the path from to .
Claim 1 yields that for every and , there is some with . Then by the definition of , . Because for each and for ; so
for every and .
Claim 2 (Distinct -sets). For all distinct , .
Proof sketch. A -path in is a path whose edges are alternately colored with and . A -path is a -path from to in .
Claim: If and , then contains an -path. The claim follows from a Kempe-chain-like argument to recolor with .
Then suppose there are with , then the -path starting at must end at both and , a contradiction.
Claim 2 yields that for every and , because the color on edge corresponds to a unique in-neighbor of (and there are no color on edge ).