Brooksの定理

頂点を $z$ からの距離 $d_G(v,z)$ の大きい順に並べ、距離が等しいものは任意の順に並べる。$z$ は距離 $0$ の唯一の頂点なので最後に来る。$v\ne z$ の距離を $m\ge1$ とし、$v$ から $z$ への最短の道で $v$ の次の頂点を $v'$ とすると、$v'$ は $v$ と隣り合い、距離は $m-1$ なので $v$ より後ろに並ぶ。$\square$

lem-brk-order の並べ方 $v_1,\dots,v_n=z$ で貪欲彩色を行う。$i< n$ のとき、$v_i$ の隣の頂点のうち少なくとも 1 つは後ろにあるので、前にある隣の頂点は $\deg(v_i)-1\le k-1$ 個以下で、$v_i$ の色は $k$ 以下である。最後の $z$ の前にある隣の頂点は $\deg(z)\le k-1$ 個以下なので、$z$ の色も $k$ 以下である。$\square$

完全グラフでない $\Delta$-正則グラフの頂点数は $\Delta+2\ge5$ 以上である（頂点数が $\Delta+1$ なら各頂点が他のすべてと隣り合い、完全グラフになる）。
$G$ が 3-連結のとき． $G$ は完全グラフでないので、隣り合わない 2 頂点 $a,b$ がある。$a$ から $b$ への最短の道 $a=q_0,q_1,\dots,q_m=b$ をとると $m\ge2$ で、$q_0$ と $q_2$ は隣り合わない（隣り合えばもっと短い道がある）。$x:=q_1$、$u:=q_0$、$w:=q_2$ とすればよい。$G-\{u,w\}$ は 3-連結性により連結である。
$G$ が 3-連結でないとき． 要点：$G$ から 1 頂点 $x$ を除いたグラフ $H$ に切断点があるようにとり、$H$ の「端」にあたる 2 つの部分 $D_1,D_2$ から $x$ の隣の頂点 $u,w$ を 1 つずつ選ぶ。

$\Delta:=\Delta(G)$ とおく。
段 1（$\Delta\le1$ は起こらない）． 頂点が 2 個以下の連結グラフは $K_1$ か $K_2$ で、完全グラフである。頂点が 3 個以上なら、頂点 $v$ をとり、$v$ から距離 $2$ の頂点があれば、そこへの最短の道の真ん中の頂点の次数は $2$ 以上であり、なければ他のすべての頂点が $v$ と隣り合うので $\deg(v)\ge2$ である。よって $\Delta\ge2$ である。
段 2（次数が $\Delta$ 未満の頂点があるとき）． lem-brk-nonregular を $k=\Delta$ として使えば、$G$ は $\Delta$-頂点彩色をもつ。以下、すべての頂点の次数が $\Delta$ であるとする。
段 3（$\Delta=2$ のとき）． 連結で次数がすべて $2$ のグラフは閉路である（閉路 の記事の命題「連結で次数がすべて 2 のグラフ」）。奇数の長さの閉路ではないので偶数の長さの閉路であり、2 色を交互に塗れば $\chi(G)=2=\Delta$ である。以下 $\Delta\ge3$ とする。
段 4（切断点 $x$ があるとき）． $G-x$ の連結成分を $C_1,\dots,C_m$（$m\ge2$）とし、$G_i:=G-\bigl(V\setminus(C_i\cup\{x\})\bigr)$ を $C_i\cup\{x\}$ が誘導する部分グラフとする。$G$ は連結なので $x$ はどの $C_j$ の頂点とも隣り合い、$G_i$ は連結である。$G_i$ の頂点の次数は $\Delta$ 以下で、$x$ は $C_i$ 以外の成分にも隣の頂点をもつので $\deg_{G_i}(x)<\Delta$ である。lem-brk-nonregular により $G_i$ は $\Delta$-頂点彩色 $c_i$ をもつ。色の名前を入れ替えて（色の集合の全単射を合成しても彩色のままである。彩色 の記事の命題「色集合の単射による彩色の移送」）$c_i(x)=1$ としてよい。$v\in C_i$ に $c_i(v)$ を、$x$ に $1$ を与える写像を $c$ とする。$G$ の辺は、異なる成分 $C_i,C_j$ の頂点を結ぶことはないので、$x$ を端点にもつか、ある $C_i$ の中にあり、いずれもある $G_i$ の辺である。よって $c$ は $G$ の $\Delta$-頂点彩色である。
段 5（切断点がないとき）． $G$ は頂点数 $\Delta+2\ge5$ 以上の 2-連結な $\Delta$-正則グラフで、完全グラフでない。lem-brk-triple により、$x$ の隣の頂点 $u,w$ で、互いに隣り合わず $G-\{u,w\}$ が連結なものがとれる。lem-brk-order を連結グラフ $G-\{u,w\}$ と頂点 $x$ に使って得た並べ方の前に $u,w$ を置き、
$$u,\ w,\ v_3,\ \dots,\ v_n=x$$
の順で貪欲彩色を行う。$u$ と $w$ は隣り合わないので、どちらも色 $1$ を受け取る。$3\le i< n$ のとき、$v_i$ は後ろに隣の頂点をもつので、前にある隣の頂点は $\Delta-1$ 個以下であり、色は $\Delta$ 以下である。最後の $x$ の隣の $\Delta$ 個の頂点はすべて前にあるが、そのうち $u,w$ は同じ色 $1$ なので、使われている色は $\Delta-1$ 種類以下であり、$\{1,\dots,\Delta\}$ の中に使われていない色が残る。よって $x$ の色も $\Delta$ 以下で、$G$ は $\Delta$-頂点彩色をもつ。$\square$

$G$ の連結成分を $G_1,\dots,G_m$ とすると $\chi(G)=\max_i\chi(G_i)$ である（彩色数 の記事の命題「部分グラフと連結成分」の 2）。$\chi(G_i)\le\Delta(G_i)+1\le\Delta+1$ なので、$\chi(G)=\Delta+1$ となるのは、ある $G_i$ で $\Delta(G_i)=\Delta$ かつ $\chi(G_i)=\Delta(G_i)+1$ となるときに限る。thm-brk-main により、そのとき $G_i$ は完全グラフか奇数の長さの閉路である。最大次数が $\Delta$ の完全グラフは $K_{\Delta+1}$ であり、閉路の最大次数は $2$ である。逆に、$K_{\Delta+1}$ の彩色数は $\Delta+1$、奇数の長さの閉路の彩色数は $3$ なので、そのような成分があれば $\chi(G)\ge\Delta+1$ である。$\square$

$G$ の辺を頂点とし、端点を共有する 2 辺を隣り合わせたグラフを線グラフ $L(G)$ とする。$G$ の辺の塗り分けは $L(G)$ の頂点彩色と同じものである（彩色 の記事の命題「辺彩色と線グラフの頂点彩色」）。辺がなければ示すことはないので、辺があるとする。
辺 $ab$ と端点を共有する他の辺は、$a$ を端点にもつ $\deg(a)-1$ 本と $b$ を端点にもつ $\deg(b)-1$ 本で、$G$ は単純グラフなので両方に属する辺はない。よって $\Delta(L(G))\le2+2=4$ である。
$L(G)$ は $K_5$ を部分グラフに含まない。実際、どの 2 本も端点を共有する $G$ の辺の集合 $F$ を考える。$F$ のすべての辺が共通の頂点 $a$ をもつなら、$|F|\le\deg(a)\le3$ である。そうでないとする。$ab\in F$ をとると、$F$ の他の辺は $a$ か $b$ を含む。共通の頂点がないので、$a$ を含まない辺 $bc\in F$（$c\ne a$）と、$b$ を含まない辺 $ad\in F$（$d\ne b$）がある。$bc$ と $ad$ は端点を共有するので $c=d$ である。$F$ のどの辺も $ab,bc,ca$ の 3 本と端点を共有する。$\{a,b,c\}$ の 1 点しか含まない辺は、その点を含まない 1 本と端点を共有しないので、$F$ の辺は $\{a,b,c\}$ の 2 点を結び、$ab,bc,ca$ のどれかである。よって $|F|\le3$ である。いずれの場合も $|F|\le3$ で、$L(G)$ に $K_5$ はない。
$L(G)$ の各連結成分 $L_i$ について $\chi(L_i)\le4$ を示せばよい（彩色数 の記事の命題「部分グラフと連結成分」の 2）。$L_i$ が完全グラフなら、$K_5$ を含まないので頂点は 4 個以下で、$\chi(L_i)\le4$ である。$L_i$ が奇数の長さの閉路なら $\chi(L_i)=3$ である。それ以外なら thm-brk-main により $\chi(L_i)\le\Delta(L_i)\le4$ である。$\square$