Vizingの定理

$G-xy_i$ の辺は、$G'$ の辺から $xy_i$ を除き $xy_0$ を加えたものなので、$c_i$ はすべての辺に色を与える。色が変わる辺はすべて $x$ を端点とし、$y_t$ は相異なるので、$x$ 以外の頂点 $v$ では、色が変わりうる辺は $xv$ の 1 本だけである。これで最後の主張が分かる。
$x$ では、$G'$ で辺 $xy_1,\dots,xy_i$ に塗られていた色 $c(xy_1),\dots,c(xy_i)$ が辺 $xy_0,\dots,xy_{i-1}$ に移り、他の辺の色は変わらない。よって $x$ に集まる辺の色の集合は $c$ のときと同じで、色は相異なり、$M_{c_i}(x)=M_c(x)$ である。$1\le t\le i$ のとき、$y_{t-1}$ では辺 $xy_{t-1}$ の色が $c(xy_t)$ になり、扇の条件によりこの色は $c$ で $y_{t-1}$ に欠けていたので、$y_{t-1}$ に集まる他の辺の色と異なる。それ以外の頂点では、集まる辺の色は $c$ と同じである（$y_i$ では辺 $xy_i$ が除かれるだけである）。よって $c_i$ は $k$-辺彩色である。$\square$

1：$x$ から色 $\beta$ の辺で始まり辺の色が交互になる歩道 $w_0w_1w_2\cdots$（$w_0=x$）は、同じ頂点を 2 度通らないことを示す。初めて同じ頂点に戻ったのが $w_j=w_i$（$i< j$）であるとする。続く 2 辺は色が異なるので異なる辺であり、$j\ge2$ である。$i\ge1$ なら、$w_i$ には辺 $w_{i-1}w_i$、$w_iw_{i+1}$、$w_{j-1}w_j$ が集まる。これらは相異なる辺である（$w_{j-1}w_j$ が前の 2 辺のどちらかと一致すれば、$w_{j-1}\in\{w_{i-1},w_{i+1}\}$ となり、$j$ より前に同じ頂点に戻っていたことになる。ここで $j-1=i+1$ の場合は、$w_iw_{i+1}$ と $w_{i+1}w_{i+2}$ が同じ辺になり、続く 2 辺の色が異なることに反する）。3 本の辺の色はどれも $\alpha$ か $\beta$ なので、2 本が同じ色になり、$c$ が辺彩色であることに反する。$i=0$ なら、$x$ には 2 辺 $w_0w_1$、$w_{j-1}w_j$ が集まる。これらは異なる辺であり（同じ辺なら $w_{j-1}=w_1$ から $j=2$ となり、続く 2 辺が同じ辺になる）、色はともに $\alpha$ か $\beta$ である。$\alpha$ は $x$ に欠けているので両方とも $\beta$ となり、やはり矛盾する。よって $P$ は道であり、$G'$ は有限なので $P$ は有限で終わる。
2：内部の頂点 $w_i$ は、$P$ の辺 $w_{i-1}w_i$ と $w_iw_{i+1}$ を色 $\alpha,\beta$ で 1 本ずつもち、各色の辺は頂点ごとに高々 1 本なので、これがすべてである。$x$ は $\alpha$ の辺をもたず、$\beta$ の辺は $P$ の最初の辺である。$w$ では、$P$ の最後の辺の色と異なる色（$\alpha$ か $\beta$）の辺 $ww'$ があれば、1 の議論により $w'$ は $P$ の頂点でなく（$P$ を $w'$ まで延ばした歩道は、いま示したことにより同じ頂点を 2 度通らない）、$P$ を延ばせることになって矛盾する。
3：2 により、$\alpha$ と $\beta$ の辺の色を入れ替えても、各頂点に集まる色 $\alpha,\beta$ の辺の本数は変わらず、その他の色の辺は変わらない。内部の頂点では $\alpha$ と $\beta$ の辺が 1 本ずつのまま、$x$ と $w$ では色 $\alpha$ または $\beta$ の辺が 1 本だけのままなので、$c'$ は辺彩色である。内部の頂点と $P$ に触れない頂点では、集まる色の集合は変わらない。$x$ では $P$ の最初の辺が $\beta$ から $\alpha$ に変わるので、$\beta\in M_{c'}(x)$ となる。$\square$

$c$ についての $x$ の極大な扇 $y_0,\dots,y_\ell$ をとる（def-vz-fan の後の段落）。仮定により $\alpha\in M_c(x)$ と $\beta\in M_c(y_\ell)$ がとれる。
場合 1：$\beta\in M_c(x)$ のとき． lem-vz-shift の $c_\ell$ をとる。$\beta$ は $M_{c_\ell}(x)=M_c(x)$ に属し、$y_\ell$ に集まる $G-xy_\ell$ の辺の色は $c$ と同じなので $y_\ell$ にも欠けている。よって $c_\ell$ に $xy_\ell\mapsto\beta$ を加えれば $G$ の $k$-辺彩色になる。
場合 2：$\beta\notin M_c(x)$ のとき． $x$ には色 $\beta$ の辺 $xz$ がある。$xy_0$ は $G'$ の辺でないので $z\ne y_0$ である。$z$ が $y_1,\dots,y_\ell$ のどれでもなければ、$c(xz)=\beta\in M_c(y_\ell)$ なので $y_0,\dots,y_\ell,z$ が扇となり、極大性に反する。よって $z=y_j$（$1\le j\le\ell$）である。$y_\ell$ には $\beta$ が欠けているので $j\ne\ell$、すなわち $1\le j\le\ell-1$ である。扇の条件から
$$ \beta=c(xy_j)\in M_c(y_{j-1}) $$
でもある。$\alpha\in M_c(x)$、$\beta\notin M_c(x)$ なので $\alpha\ne\beta$ であり、lem-vz-swap の道 $P$ とその端点 $w$、入れ替えた辺彩色 $c'$ が定まる。$P$ の $x$ での辺は色 $\beta$ の辺 $xy_j$ である。
$y_{j-1}$ と $y_\ell$ にはどちらも $\beta$ が欠けているので、色 $\alpha$ または $\beta$ の辺を高々 1 本しかもたない。lem-vz-swap の 2 により、これらが $P$ の頂点なら $P$ の内部の頂点ではありえず、$x$ とも異なるので、端点 $w$ である。$j-1\ne\ell$ なので、$y_{j-1}$ と $y_\ell$ のうち $P$ の頂点になるのは高々一方である。
$c$ と $c'$ で色が異なるのは $P$ の辺だけで、$x$ を端点とする $P$ の辺は $xy_j$ だけである。$t\ne j$ のとき、$c(xy_t)$ は $\beta$ でなく（$\beta$ の辺は $xy_j$ だけ）、$\alpha$ でもない（$\alpha$ は $x$ に欠けている）。lem-vz-swap の 3 により $M_{c'}$ と $M_c$ の違いは $\alpha,\beta$ の出入りだけなので、$t\ne j$ について $c'(xy_t)=c(xy_t)\in M_{c'}(y_{t-1})$ がなお成り立つ。また $\beta\in M_{c'}(x)$ である。
場合 2a：$y_{j-1}$ が $P$ の頂点でないとき． $y_{j-1}$ に集まる辺の色は変わらないので $\beta\in M_{c'}(y_{j-1})$ である。上のことから $y_0,\dots,y_{j-1}$ は $c'$ についての扇である。lem-vz-shift を $c'$ とこの扇に使って $c'_{j-1}$ をとると、$\beta$ は $M_{c'_{j-1}}(x)=M_{c'}(x)$ に属し、$y_{j-1}$ にも欠けている。$c'_{j-1}$ に $xy_{j-1}\mapsto\beta$ を加えれば $G$ の $k$-辺彩色になる。
場合 2b：$y_{j-1}$ が $P$ の頂点のとき． このとき $y_{j-1}=w$ で、$y_\ell$ は $P$ の頂点でないので $\beta\in M_{c'}(y_\ell)$ である。$w=y_{j-1}$ には $\beta$ が欠けているので、$P$ の最後の辺の色は $\alpha$ であり、入れ替えで $\beta$ になる。$y_{j-1}$ の色 $\alpha$ の辺はこの 1 本だけだったので、$\alpha\in M_{c'}(y_{j-1})$ となる。一方 $c'(xy_j)=\alpha$ なので、扇の条件は $t=j$ でも成り立ち、$y_0,\dots,y_\ell$ は $c'$ についての扇である。lem-vz-shift で $c'_\ell$ をとると、$\beta$ は $x$ にも $y_\ell$ にも欠けているので、$c'_\ell$ に $xy_\ell\mapsto\beta$ を加えれば $G$ の $k$-辺彩色になる。$\square$

下界 $\Delta(G)\le\chi'(G)$ は、最大次数の頂点に集まる $\Delta(G)$ 本の辺が互いに異なる色を要することによる（辺彩色 の記事の命題「辺彩色数の基本評価」）。上界 $\chi'(G)\le\Delta(G)+1$ を辺の本数についての帰納法で示す。辺がなければ $\chi'(G)=0$ である。辺 $xy_0$ をとり、$G':=G-xy_0$ とする。$\Delta(G')\le\Delta(G)$ なので、帰納法の仮定により $G'$ は $(\Delta(G')+1)$-辺彩色をもち、色の集合を広げれば $k:=\Delta(G)+1$ について $k$-辺彩色 $c$ をもつ。$G'$ のどの頂点 $v$ でも $\deg_{G'}(v)\le\Delta(G)< k$ なので、$v$ には欠けている色がある。とくに $x$ と $x$ のすべての隣接頂点に欠けている色があり、lem-vz-fan により $G$ は $k$-辺彩色をもつ。$\square$

$k:=\Delta(G)\ge1$ を固定し、「$\Delta(H)\le k$ で、次数が $k$ の頂点どうしが隣り合わないグラフ $H$ は $k$-辺彩色をもつ」ことを $H$ の辺の本数についての帰納法で示す。辺がなければ明らかである。$H$ に次数 $k$ の頂点がなければ $\Delta(H)\le k-1$ であり、thm-vz-main により $\chi'(H)\le k$ である。
次数 $k$ の頂点 $x$ があるとき、$x$ の辺 $xy_0$ をとり $H':=H-xy_0$ とする。$H'$ の各頂点の次数は $H$ での次数以下で、$H'$ で次数 $k$ の頂点は $H$ でも次数 $k$ であり、$H'$ の辺は $H$ の辺なので、$H'$ も仮定を満たす。帰納法の仮定により $H'$ は $k$-辺彩色 $c$ をもつ。$\deg_{H'}(x)=k-1$ なので $x$ には欠けている色がある。$x$ の隣接頂点 $z$ は、$x$ と隣り合うので次数 $k$ でなく、$\deg_{H'}(z)\le\deg_H(z)\le k-1$ なので、欠けている色をもつ。lem-vz-fan により $H$ は $k$-辺彩色をもつ。
$H=G$ とすれば $\chi'(G)\le\Delta(G)$ であり、逆の不等式は thm-vz-main の下界である。$\square$