無限グラフ

$n\ge1$ と $v\in V_n$ について、$v$ と隣接する $V_{n-1}$ の頂点を 1 つ選んで $p(v)$ とする（各 $V_n$ の元に番号を付けておき、番号の最小のものをとる。後の $v_{n+1}$ も同じく番号の最小のものをとる。頂点に初めから番号があれば（たとえば可算グラフ）選択は要らないが、一般には可算個の有限集合に番号を付けるところで選択公理の弱い形を使う）。$m\ge n$、$u\in V_m$、$v\in V_n$ について、$p$ を $m-n$ 回施して $u$ から $v$ に着くとき、$u$ を $v$ の子孫という（$u=v$ も含める）。$V_m$ の各頂点は、各 $n\le m$ について $V_n$ のちょうど 1 つの頂点の子孫である。
$V_0$ の頂点の子孫を全部合わせると、すべての頂点になる。頂点は無限個あり（$V_n$ はどれも空でない）、$V_0$ は有限なので、子孫が無限に多い $v_0\in V_0$ がある。$v_n\in V_n$ の子孫が無限に多いとする。$v_n$ 以外の $v_n$ の子孫は、$p(w)=v_n$ となる $w\in V_{n+1}$ のどれかの子孫である。そのような $w$ は有限個なので、子孫が無限に多い $w$ があり、それを $v_{n+1}$ とする。$v_{n+1}$ と $v_n=p(v_{n+1})$ は隣接し、$V_n$ が互いに交わらないので $v_0,v_1,\dots$ は相異なる。よって $v_0v_1v_2\cdots$ は半無限道である。$\square$

$G$ が局所有限であるとし、頂点 $v_0$ を 1 つ固定する。$n\ge0$ について、$v_0$ からの距離（距離(グラフ)）が $n$ の頂点の集合を $V_n$ とする。$G$ は連結なので、すべての頂点はどれかの $V_n$ に属する。
$V_0=\{v_0\}$ は有限であり、$V_{n+1}$ の頂点は $V_n$ のある頂点と隣接する（$v_0$ への最短の道の上で 1 つ手前の頂点）。よって $V_{n+1}$ は $V_n$ の頂点の隣接点の集合の和に含まれ、局所有限性から、$V_n$ が有限なら $V_{n+1}$ も有限である。帰納法ですべての $V_n$ は有限である。
ある $N$ で $V_N=\emptyset$ なら、距離が $N$ 以上の頂点は、$v_0$ への最短の道の上に距離 $N$ の頂点をもつので存在せず、$G$ の頂点は $V_0\cup\cdots\cup V_{N-1}$ に含まれ有限個になって仮定に反する。よってすべての $V_n$ は空でない。
lem-ig-infinity-lemma により、$v_n\in V_n$ となる半無限道 $v_0v_1v_2\cdots$ がある。$v_0$ は任意だったので、最後の主張も従う。$\square$

後戻りのない歩道は道．$T$ の歩道 $x_0x_1x_2\cdots$（有限でも無限でもよい）で、すべての $i\ge1$ について $x_{i+1}\ne x_{i-1}$ となるものの頂点は相異なる。$x_i=x_j$（$i< j$）となる組のうち $j-i$ が最小のものをとると、$x_i,\dots,x_{j-1}$ は相異なる。$j-i=1$ はループ、$j-i=2$ は $x_{i+2}=x_i$ で後戻りになるので、$j-i\ge3$ であり、$x_ix_{i+1}\cdots x_j$ は閉路になって $T$ が閉路をもたないことに反する。
半無限道．頂点 $x_0$ と隣接点 $x_1$ を選ぶ。$x_n$ まで決めたら、$x_n$ の次数が $2$ 以上なので $x_{n-1}$ 以外の隣接点 $x_{n+1}$ を選ぶ。こうしてできる歩道は後戻りがないので、$x_0x_1x_2\cdots$ は半無限道である。
両側無限道．辺 $x_0x_1$ をとり、$x_1$ から $x_0$ を通らない側へ、$x_0$ から $x_1$ を通らない側へ、同じ手順で後戻りなしに延ばす（$x_0$ の側を $x_{-1},x_{-2},\dots$ とする）。両側をつないだ $\cdots x_{-1}x_0x_1\cdots$ も後戻りがないので頂点は相異なり、両側無限道である。$\square$

$E(G)$ の部分集合 $F$ で、グラフ $(V(G),F)$ が閉路をもたないもの全体を $\mathcal P$ とし、包含関係で順序を入れる。$\emptyset\in\mathcal P$ なので空でない。
鎖の上界．$\mathcal C\subset\mathcal P$ を空でない鎖とし、$F^{*}:=\bigcup\mathcal C$ とする。$(V(G),F^{*})$ が閉路 $C$ をもったとする。$C$ の辺は有限個で、それぞれ $\mathcal C$ のどれかの元に属する。それら有限個の元は鎖をなすので最大のもの $F$ があり、$C$ の辺はすべて $F$ に属する。これは $F\in\mathcal P$ に反する。よって $F^{*}\in\mathcal P$ で、$F^{*}$ は $\mathcal C$ の上界である。Zornの補題 の記事の定理「鎖の上界から得られる極大元」により、$\mathcal P$ は極大元 $F$ をもつ。
極大なら連結．$T:=(V(G),F)$ が連結でなかったとする。$T$ の連結成分 $C$ を 1 つとると $\emptyset\ne V(C)\ne V(G)$ である。$G$ は連結なので、連結グラフ の記事の命題「切断による判定」により、$u\in V(C)$、$v\notin V(C)$ となる辺 $uv\in E(G)$ がある。$uv\notin F$ である。$F\cup\{uv\}$ に閉路があれば、その閉路は $uv$ を通るので、閉路から $uv$ を除いた $T$ の道が $v$ と $u$ を結び、$u,v$ が $T$ の異なる連結成分にあることに反する。よって $F\cup\{uv\}\in\mathcal P$ となり、$F$ の極大性に反する。したがって $T$ は連結で閉路をもたない、すなわち全域木である。$\square$

頂点を $u_0,u_1,u_2,\dots$ と並べ、$G_n$ を $\{u_0,\dots,u_n\}$ が誘導する部分グラフとする。$V_n$ を、$G_n$ の頂点彩色で色を $\{1,\dots,k\}$ からとるもの（写像 $\{u_0,\dots,u_n\}\to\{1,\dots,k\}$）の集合とする。仮定から $V_n$ は空でなく、写像の個数は $k^{n+1}$ 以下なので有限である。$c\in V_n$（$n\ge1$）と、その $\{u_0,\dots,u_{n-1}\}$ への制限 $c'\in V_{n-1}$ を辺で結ぶ。$G_{n-1}$ は $G_n$ の誘導部分グラフなので $c'$ は確かに $G_{n-1}$ の彩色である。lem-ig-infinity-lemma により半無限道 $c_0c_1c_2\cdots$（$c_n\in V_n$）がある。$c_n$ は $c_{n+1}$ の制限なので、$c(u_n):=c_n(u_n)$ と定めると、すべての $m\ge n$ で $c_m(u_n)=c(u_n)$ である。$G$ の辺 $u_iu_j$ について $m=\max\{i,j\}$ とすれば $c(u_i)=c_m(u_i)\ne c_m(u_j)=c(u_j)$ なので、$c$ は $G$ の $k$ 色の頂点彩色である。$\square$

$U,W\subset\mathbb N$ を互いに交わらない有限集合とし、$U\cup W$ のどの元よりも大きい $m\in\mathbb N$ をとる（$U\cup W=\emptyset$ なら $m=0$）。$v:=2^m+\sum_{u\in U}2^u$ とおく。$v\ge2^m>m$ なので $v$ は $U\cup W$ のどの元よりも大きく、$U\cup W$ に属さない。$v$ の 2 進法の第 $i$ 桁が $1$ であるのは $i\in U$ または $i=m$ のときちょうどである。$u\in U$ は $u< v$ で第 $u$ 桁が $1$ なので $v$ と隣接する。$w\in W$ は $w< v$ で $w\notin U$、$w\ne m$ だから第 $w$ 桁が $0$ なので $v$ と隣接しない。$\square$

$G$ の頂点を $g_0,g_1,g_2,\dots$ と並べる。単射 $\varphi$ を $g_0,g_1,\dots$ の順に定義する。$g_0,\dots,g_{n-1}$ の像まで決まったとき、
$$ U:=\{\varphi(g_i)\mid i< n,\ g_ig_n\in E(G)\},\qquad W:=\{\varphi(g_i)\mid i< n,\ g_ig_n\notin E(G)\} $$
とおく。$\varphi$ はそれまで単射なので $U$ と $W$ は交わらない有限集合で、$U\cup W$ はそれまでの像全体である。拡大性により、$U\cup W$ の外の頂点で $U$ のすべてと隣接し $W$ のどれとも隣接しないものがあるので、その 1 つを $\varphi(g_n)$ とする（$R'$ の頂点が可算なら、番号最小のものをとればよい）。
$\varphi(g_n)$ はそれまでの像と異なるので $\varphi$ は単射である。$i< n$ について、$g_ig_n\in E(G)$ なら $\varphi(g_i)\in U$ で $\varphi(g_n)$ と隣接し、$g_ig_n\notin E(G)$ なら $\varphi(g_i)\in W$ で隣接しない。よって $\varphi$ は $G$ から、像が誘導する $R'$ の部分グラフへの同型である。$\square$

どちらも拡大性をもたないとすると、$V_1$ の中に拡大性の要求を満たさない組 $U_1,W_1$ が、$V_2$ の中に組 $U_2,W_2$ がある。$U:=U_1\cup U_2$、$W:=W_1\cup W_2$ は互いに交わらない有限集合なので、$R'$ の拡大性から、$U\cup W$ の外の頂点 $v$ で $U$ のすべてと隣接し $W$ のどれとも隣接しないものがある。$v\in V_1$ なら $v$ は $U_1\cup W_1$ の外にあって $U_1$ のすべてと隣接し $W_1$ のどれとも隣接せず、$U_1,W_1$ の選び方に反する。$v\in V_2$ でも同様である。後半は、拡大性をもつ可算グラフが $R$ と同型であることから従う（拡大性をもつ部分は無限で、$R$ の部分なので可算である）。$\square$