Graph coloring theorems revisited II – Vizing’s Theorem

Alexandr Kostochka found the following new proof to the classical theorem.

Vizing’s Theorem.  For every simple graph $G$, $\chi'(G) \le \Delta(G) + 1$.

Proof.  We prove by contradiction; assume that $G$ is a minimal counter-example (in terms of number of edges) to the statement; that is, $G$ has no edge-($\Delta+1$)-coloring.

Let $\phi$ be an edge-($\Delta+1$)-coloring of $G-xy$. For every $v \in V(G)$, let $O(v)=O_\phi(v)$ denote the set of colors in $[\Delta+1]$ not used to color the edges incident to $v$; one can see that $O(x) \cap O(y) = \emptyset$.

Construct the auxiliary multidigraph $H$ as follows: $V(H) = N_G(y)$ and there is a directed edge from $u$ to $v$ in $E(H)$ if $\phi(vy) \in O(u)$. Intuitively an edge from $u$ to $v$ means that if we can recolor $vy$, then we can recolor $uy$ as well. Let $X$ be the set of vertices reachable in $H$ from $x$ ($x \in X$ as well); any recoloring of an edge $wy$ for $w\in X$ will imply that we can color $xy$. Since the out-neighbors of a vertex reachable from $x$ also are reachable from $x$, $N^+_H(v) \subseteq X$ for every $v \in X$.  Therefore

$\sum_{v \in X} d^+_{H[X]}(v) = |{E(H[X])}| = \sum_{v \in X} d^-_{H[X]}(v) \text,$

and the theorem will be proven if we can show that

1. $d^+_{H[X]}(v) \ge \Delta - d(v) + 1 + [v = x]$ and
2. $d^-_{H[X]}(v) \le 1-[v=x]$ for all $v \in X$;

this implies

$0 = \sum_{v \in X} \{d^+_{H[X]}(v) - d^-_{H[X]}(v)\} \ge 2 + \sum_{v \in X} (\Delta - d(v)) \ge 2$,

a contradiction.  Items (1) and (2) follow from the following claims. Let $\alpha \in O(y)$.

Claim 1 (Exchange argument).  $\alpha\notin O(v)$ for every $v\in X$.
Proof sketch.  Recolor the edges of the form $wy$ for each $w$ on the path from $x$ to $v$.

Claim 1 yields that for every $v \in X$ and $\beta \in O(v)$, there is some $w \in N(y)$ with $\phi(yw)=\beta$. Then by the definition of $H$, $vw\in H[X]$. Because $|{O(v)}| \ge \Delta+1-d(v)$ for each $v\in V(G)$ and $|{O(u)}| \ge \Delta+1-d_{G-xy}(u) = \Delta-d(u)+2$ for $u \in\{x,y\}$; so

$d^+_{H[X]}(v) \ge \Delta+1-d(v)$ for every $v \in X$ and $d^+_{H[X]}(x) \ge \Delta-d(x)+2$.

Claim 2 (Distinct $O$-sets).  For all distinct $v,w \in X$, $O(v) \cap O(w) = \emptyset$.
Proof sketch.  A $[\beta,\gamma]$-path in $G$ is a path whose edges are alternately colored with $\beta$ and $\gamma$. A $[\beta,\gamma](a,b)$-path is a $[\beta,\gamma]$-path from $a$ to $b$ in $G$.

Claim: If $v \in X$ and $\beta \in O(v)$, then $G$ contains an $[\alpha,\beta](v,y)$-path.  The claim follows from a Kempe-chain-like argument to recolor $vy$ with $\alpha$.

Then suppose there are $v,w\in X$ with $\beta\in O(v)\cap O(w)$, then the $[\beta,\alpha]$-path starting at $y$ must end at both $v$ and $w$, a contradiction.

Claim 2 yields that $d^-_{H[X]}(v) \le 1$ for every $v \in X$ and $d^-_{H[X]}(x) = 0$, because the color on edge $vy$ corresponds to a unique in-neighbor of $v$ (and there are no color on edge $xy$).

Author: hcsoso

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