多重グラフ

$(\theta,\varphi)$ が同型なら、$\varphi$ は $\partial(e)=\{u,v\}$ となる辺全体を $\partial'(e')=\{\theta(u),\theta(v)\}$ となる辺全体へ全単射に写すので、多重度は等しい。逆に $\theta$ が多重度を保つとする。$V$ の 1 元または 2 元の部分集合 $p$ ごとに、$E_p:=\{e\mid\partial(e)=p\}$ と $E'_{\theta(p)}$ は同じ個数の有限集合なので、全単射 $\varphi_p\colon E_p\to E'_{\theta(p)}$ がとれる。$E$ は $E_p$ たちの交わらない和であり、$E'$ も $E'_{\theta(p)}$ たちの交わらない和なので、$\varphi_p$ をつなげた $\varphi\colon E\to E'$ は全単射であり、$(\theta,\varphi)$ は同型である。$\square$

1 は単純化の定義そのものである。
2：$G$ の歩道 $v_0,e_1,v_1,\dots,e_\ell,v_\ell$ から、ループ $e_i$（このとき $v_{i-1}=v_i$）を通る段を取り除くと、残った頂点の列の隣り合う 2 頂点は相異なり、1 により $G^{\mathrm s}$ で隣接する。よってこれは $G^{\mathrm s}$ の同じ 2 頂点を結ぶ歩道である。逆に $G^{\mathrm s}$ の歩道 $v_0,\dots,v_\ell$ の各段 $v_{i-1}v_i$ に対し、1 により $\partial(e_i)=\{v_{i-1},v_i\}$ となる $G$ の辺 $e_i$ を選べば、$v_0,e_1,v_1,\dots,e_\ell,v_\ell$ は $G$ の歩道である。
3：$\deg_{G^{\mathrm s}}(v)$ は $v$ に隣接する頂点の個数であり、これは $v$ に接続するループでない辺 $e$ の端点の対 $\partial(e)$ の相異なるものの個数に等しい。したがって $\deg_{G^{\mathrm s}}(v)$ は、$v$ に接続するループでない辺の本数以下であり、それは $\deg_G(v)$ 以下である。$v$ で等号が成り立つのは、$v$ にループがなく、かつ $v$ に接続するループでない辺の $\partial$ の値が互いに異なる（$v$ を端点とする平行辺がない）ときに限る。$G$ がループも平行辺も持たなければすべての $v$ でこれが成り立つ。逆にすべての $v$ で等号が成り立てば、ループはなく、平行辺 $e\neq e'$、$\partial(e)=\partial(e')=\{u,w\}$ があれば $u$ で不等号が真になるので、平行辺もない。$\square$

$s:=d_1+\dots+d_n$ とおく。どちらの場合も、$s$ が偶数であることの必要性は次数の総和が辺の本数の 2 倍であること（次数(グラフ) の記事の定理「次数の総和と辺数」）による。
1 の十分性：$s$ が偶数なら、奇数の $d_i$ は偶数個ある。各 $v_i$ に $\lfloor d_i/2\rfloor$ 本のループを置き、奇数の $d_i$ を持つ頂点を 2 個ずつ組にして、各組を 1 本の辺で結ぶ。ループは次数に $2$ ずつ加えるので、$v_i$ の次数は $2\lfloor d_i/2\rfloor$ に、奇数なら $1$ を加えたもの、すなわち $d_i$ になる。
2 の必要性：$v_1$ に接続する辺はループでないので、それぞれ $v_1$ 以外にもう 1 つの端点を持ち、その端点の次数に $1$ を加える。よって $d_1$ は $v_2,\dots,v_n$ の次数の和以下である。
2 の十分性：$s$ についての帰納法による。$s=0$ なら辺のない多重グラフでよい。$s>0$ とし、$s$ より小さい総和の列では主張が成り立つとする。$d_1>0$ であり、$d_1\le d_2+\dots+d_n$ から $d_2+\dots+d_n\ge1$、したがって $d_2\ge1$ である。$d_1,d_2$ をそれぞれ $1$ 減らした列を並べ替えて、新しい列 $(d'_1,\dots,d'_n)$ を作る。その総和は $s-2$ で偶数である。新しい列の最大値を $M'$ とし、$2M'\le s-2$（最大値が残りの和以下であることと同値）を示す。

• $M'=d_1-1$ の場合：$2d_1\le s$ から $2(d_1-1)\le s-2$ である。
• $M'\neq d_1-1$ の場合：$M'$ は $d_2-1$ でもない（$d_2-1\le d_1-1$）ので、$M'=d_3>d_1-1$（$n\ge3$）であり、$d_1\ge d_2\ge d_3\ge d_1$ から $d_1=d_2=d_3=M'$ である。$s\ge3M'$ なので、$M'\ge2$ なら $s-2\ge3M'-2\ge2M'$ である。$M'=1$ なら $s\ge3$ で $s$ は偶数なので $s\ge4$、よって $s-2\ge2=2M'$ である。
  帰納法の仮定により、新しい列を次数列とするループのない多重グラフがある。その中で、次数が $d_1-1$、$d_2-1$ にあたる頂点を $v_1,v_2$ とし、$v_1$ と $v_2$ を結ぶ辺を 1 本加えれば、ループを作らずに次数列 $(d_1,\dots,d_n)$ が得られる。$\square$

どの辺も $X$ の頂点をちょうど 1 つ端点に持つので $\lvert E\rvert=k\lvert X\rvert$、同様に $\lvert E\rvert=k\lvert Y\rvert$ であり、$k\ge1$ から $\lvert X\rvert=\lvert Y\rvert$ である。$S\subset X$ とし、$S$ に隣接する頂点の集合を $N(S)$ とする。$S$ の頂点に接続する辺はちょうど $k\lvert S\rvert$ 本あり、その $Y$ 側の端点はすべて $N(S)$ に属するので、これらは $N(S)$ の頂点に接続する $k\lvert N(S)\rvert$ 本の辺の一部である。よって $\lvert N(S)\rvert\ge\lvert S\rvert$ である。
$H$ の単純化 $H^{\mathrm s}$ は部集合 $X,Y$ の二部グラフで、各頂点の隣接頂点の集合は $H$ と同じなので、$H^{\mathrm s}$ でも $\lvert N(S)\rvert\ge\lvert S\rvert$ がすべての $S\subset X$ について成り立つ。マッチング(グラフ理論) の記事の定理「Hall の条件によるマッチングの存在」により、$H^{\mathrm s}$ には $X$ の頂点をすべて端点に持つマッチング $M^{\mathrm s}$ がある。$M^{\mathrm s}$ の各辺 $xy$ について、$H$ で $x,y$ を結ぶ辺を 1 本ずつ選べば $H$ のマッチングが得られ、$\lvert X\rvert=\lvert Y\rvert$ なのでそれは完全マッチングである。$\square$

1 頂点に接続する辺は互いに端点を共有するので $\chi'(G)\ge\Delta$ である。$\Delta=0$ なら辺がないので $\chi'(G)=0$ である。以下 $\Delta\ge1$ とし、部集合を $X,Y$ とする。
段 1（正則な多重グラフへの埋め込み）。頂点の少ない側に孤立点を加えて $\lvert X\rvert=\lvert Y\rvert$ とする。次の操作を繰り返す：次数が $\Delta$ 未満の頂点があれば、それを $X$ 側の $x$ とし（$Y$ 側なら役割を入れ替える）、次数が $\Delta$ 未満の $y\in Y$ を選んで、$x$ と $y$ を結ぶ辺を 1 本加える。そのような $y$ は必ずある。実際、$X$ 側の次数の和も $Y$ 側の次数の和も辺の本数に等しく、$X$ 側の和は $\Delta\lvert X\rvert$ 未満なので、$Y$ 側の和も $\Delta\lvert Y\rvert=\Delta\lvert X\rvert$ 未満だからである。加える辺は既存の辺と平行になりうるが、ループにはならず、二部性と「次数が $\Delta$ 以下」は保たれる。辺の本数は毎回 $1$ 増え、$\Delta\lvert X\rvert$ を超えないので、操作は有限回で止まる。止まったとき、すべての頂点の次数が $\Delta$ の二部多重グラフ $G^*$ が得られ、$G$ はその部分グラフである。
段 2（完全マッチングへの分解）。$\Delta$ についての帰納法で、$\Delta$ 正則なループのない二部多重グラフの辺集合は、$\Delta$ 個の完全マッチング $M_1,\dots,M_\Delta$ の交わらない和であることを示す。$\Delta=1$ なら辺集合そのものが完全マッチングである。$\Delta\ge2$ なら lem-multigraph-regular-matching により完全マッチング $M_1$ があり、$M_1$ の辺を除くと各頂点の次数がちょうど $1$ 減って $(\Delta-1)$ 正則な二部多重グラフになるので、帰納法の仮定が使える。
段 3。$G^*$ の辺集合を段 2 のように $M_1,\dots,M_\Delta$ に分け、$M_i$ の辺に色 $i$ を塗る。同じ色の辺はマッチングに属するので端点を共有せず、これは $G^*$ の $\Delta$ 色の辺彩色である。それを $G$ の辺に制限すれば $G$ の辺彩色が得られ、$\chi'(G)\le\Delta$ である。$\square$

段 1（向き付け）。$G$ の各連結成分 $C$ は、すべての頂点の次数が $2k\ge2$ なので辺を持ち、次数はすべて偶数である。Euler閉路 の記事の定理「Euler の定理」により、$C$ は Euler 閉路 $W=(w_0,e_1,w_1,\dots,e_\ell,w_\ell)$（$w_\ell=w_0$）を持つ。各辺 $e_i$ に $w_{i-1}$ から $w_i$ への向きを付ける。ループがないので $w_{i-1}\neq w_i$ である。頂点 $v$ から出る辺の本数は $w_{i-1}=v$ となる $i$（$1\le i\le\ell$）の個数、$v$ に入る辺の本数は $w_i=v$ となる $i$ の個数である。$w_\ell=w_0$ なので列 $(w_0,\dots,w_{\ell-1})$ と $(w_1,\dots,w_\ell)$ は同じ頂点を同じ回数含み、出る辺と入る辺の本数は等しい。$W$ は $v$ に接続する $2k$ 本の辺をちょうど 1 回ずつ通り、各辺は $v$ から出るか $v$ に入るかのちょうど一方なので、出る辺も入る辺も $k$ 本である。すべての成分で向きを付ける。
段 2（二部多重グラフ）。各頂点 $v$ を 2 つの頂点 $v^+,v^-$ に分け、$V^+:=\{v^+\}$、$V^-:=\{v^-\}$ を部集合とする多重グラフ $H$ を、$G$ と同じ辺集合 $E$ と、$u$ から $w$ へ向いた辺 $e$ に $\partial_H(e):=\{u^+,w^-\}$ を与えて作る。$H$ はループのない二部多重グラフで、$\deg_H(v^+)$ は $v$ から出る辺の本数、$\deg_H(v^-)$ は $v$ に入る辺の本数なので、$H$ の次数はすべて $k$ である。lem-multigraph-regular-matching により、$H$ は完全マッチング $F\subset E$ を持つ。
段 3（2-因子）。$G$ の頂点 $v$ に接続する $F$ の辺を数える。$v$ に接続する辺は、$v$ から出る辺（$H$ で $v^+$ に接続する）か $v$ に入る辺（$H$ で $v^-$ に接続する）のちょうど一方である。$F$ は $H$ の完全マッチングなので、$F$ のうち $v^+$ に接続する辺と $v^-$ に接続する辺はちょうど 1 本ずつある。よって $F$ のうち $v$ に接続する辺はちょうど 2 本であり、$F$ は $G$ の 2-因子である。
段 4（分解）。$k$ についての帰納法による。$k=1$ なら $E$ 自身が 2-因子である。$k\ge2$ なら段 3 の 2-因子 $F$ を除いた多重グラフ $(V,E\setminus F)$ の次数はすべて $2(k-1)$ であり、帰納法の仮定によりその辺集合は $k-1$ 個の 2-因子の交わらない和である。$F$ を加えれば主張を得る。$\square$