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

- and
- for all ;

this implies

,

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 ).

### Like this:

Like Loading...

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.