グラフ準同型

写像 $c\colon V(G)\to\{1,\dots,k\}$ が準同型 $G\to K_k$ であることは、$uv\in E(G)$ ならば $c(u)c(v)$ が $K_k$ の辺、すなわち $c(u)\ne c(v)$ であることで、これは $c$ が頂点彩色であることの定義そのものである（彩色 の記事の定義「頂点彩色」）。よって両者は同じ写像の集合で、個数も等しい。$k$ 色以下の頂点彩色は色を $\{1,\dots,k\}$ の中から選べば $k$ 色の写像とみなせるので、最初の主張が従う。$\square$

$m$ についての帰納法で示す。閉じた歩道 $x_0x_1\cdots x_{m-1}x_0$ の頂点 $x_0,\dots,x_{m-1}$ が相異なれば、$m\ge3$ なのでこれは長さ $m$ の閉路である（$m=1$ は辺 $x_0x_0$ がループになり起こらない）。ある $i< j$ で $x_i=x_j$ なら、歩道は $x_i\cdots x_j$（長さ $j-i$）と、$x_j\cdots x_{m-1}x_0\cdots x_i$（長さ $m-(j-i)$）の 2 つの閉じた歩道に分かれる。長さの和は奇数 $m$ なので一方は奇数で、$m$ より短い。帰納法の仮定をその歩道に使えばよい。$\square$

$f\colon G\to H$ とする。
彩色数．$k=\chi(H)$ として $H\to K_k$ の準同型 $c$ をとると、$c\circ f\colon G\to K_k$ なので、prop-ghom-coloring により $\chi(G)\le k$ である。
クリーク数．$G$ のクリーク $Q$ の 2 頂点は隣接するので、像は異なり隣接する。よって $f(Q)$ は $\lvert Q\rvert$ 個の頂点からなる $H$ のクリークで、$\omega(G)\le\omega(H)$ である。
奇内周．$\mathrm{og}(G)=\infty$ なら明らかである。$G$ の長さ $m$（奇数）の閉路 $x_0\cdots x_{m-1}x_0$ の像 $f(x_0)\cdots f(x_{m-1})f(x_0)$ は $H$ の長さ $m$ の閉じた歩道なので、lem-ghom-odd-walk により $H$ は長さ $m$ 以下の奇数の長さの閉路をもつ。$m=\mathrm{og}(G)$ とすれば $\mathrm{og}(H)\le\mathrm{og}(G)$ である。$\square$

$C_{2k+1}$ の頂点を $0,1,\dots,2k$、$C_{2l+1}$ の頂点を $0,1,\dots,2l$ とし、それぞれ隣り合う番号と、最後の番号と $0$ を結ぶ。
$k\ge l$ とする。$f(i):=i$（$0\le i\le2l$）とし、$2l< i\le2k$ では $i$ が奇数なら $f(i):=0$、偶数なら $f(i):=2l$ とする。$C_{2k+1}$ の辺 $\{i,i+1\}$（$0\le i< 2l$）は辺 $\{i,i+1\}$ に写る。$2l\le i< 2k$ の辺 $\{i,i+1\}$ は、$i,i+1$ の一方が $0$ に、他方が $2l$ に写るので、$C_{2l+1}$ の辺 $\{2l,0\}$ に写る。最後の辺 $\{2k,0\}$ は、$2k$ が偶数なので $\{2l,0\}$ に写る（$k=l$ のときも $f(2k)=2l$）。よって $f$ は準同型である。
逆に $C_{2k+1}\to C_{2l+1}$ なら、prop-ghom-monotone により $2k+1=\mathrm{og}(C_{2k+1})\ge\mathrm{og}(C_{2l+1})=2l+1$ である。$\square$

$\varphi\colon H_1\to H_2$、$\psi\colon H_2\to H_1$ とする。$\psi\circ\varphi$ は $H_1$ の自己準同型なので全単射であり、とくに $\varphi$ は頂点について単射である。同様に $\varphi\circ\psi$ から $\psi$ も単射である。よって $\lvert V(H_1)\rvert=\lvert V(H_2)\rvert$ で、$\varphi$ は頂点の全単射である。単射な準同型は辺の集合を辺の集合へ単射に写すので、$\varphi$ と $\psi$ から $\lvert E(H_1)\rvert\le\lvert E(H_2)\rvert\le\lvert E(H_1)\rvert$ となり、$\varphi$ は辺の集合の全単射でもある。したがって $\varphi^{-1}$ も辺を辺に写し、$\varphi$ は同型である。$\square$

1．$G\to H$ となる $G$ の部分グラフ $H$ 全体は $G$ 自身を含むので空でない。その中で頂点の個数が最小のものを $H$ とし、$f\colon G\to H$ をとる。$H$ の自己準同型 $g$ が全単射でなかったとする。$H$ は有限なので $g$ は頂点について全射でなく、$g$ の像 $H'$（頂点 $g(V(H))$、辺 $\{g(u)g(v)\mid uv\in E(H)\}$）は $H$ の部分グラフで頂点が $H$ より少ない。$g\circ f\colon G\to H'$ なので、$H$ の最小性に反する。よって $H$ はコアである。
$H$ を $G$ の任意のコアとし、$f\colon G\to H$ をとる。$f$ を $H$ に制限した写像は $H$ の自己準同型なので自己同型 $\sigma$ である。$r:=\sigma^{-1}\circ f$ は準同型 $G\to H$ で、$H$ の頂点 $x$ について $r(x)=\sigma^{-1}(\sigma(x))=x$ である。
2．$H_1,H_2$ を $G$ のコアとする。$H_1\subset G\to H_2$ と $H_2\subset G\to H_1$（包含のあとに準同型を合成する）から、lem-ghom-equivalent-cores により $H_1\cong H_2$ である。
3．$G$ と $\mathrm{core}(G)$ は、$G\to\mathrm{core}(G)$ と包含 $\mathrm{core}(G)\to G$ により準同型同値である。$G'$ についても同様である。$\mathrm{core}(G)\cong\mathrm{core}(G')$ なら $G\to\mathrm{core}(G)\cong\mathrm{core}(G')\to G'$ で、逆向きも同様なので、$G$ と $G'$ は準同型同値である。逆に $G$ と $G'$ が準同型同値なら、$\mathrm{core}(G)\to G\to G'\to\mathrm{core}(G')$ と逆向きの合成があるので、lem-ghom-equivalent-cores により $\mathrm{core}(G)\cong\mathrm{core}(G')$ である。$\square$

$uv\in E(F)$ について、$f(u)f(v)$ が $G\times H$ の辺であることは、定義により $f_1(u)f_1(v)\in E(G)$ かつ $f_2(u)f_2(v)\in E(H)$ であることである。これがすべての辺で成り立つことが、両辺の条件である。準同型 $F\to G\times H$ は準同型の組 $(f_1,f_2)$ と 1 対 1 に対応するので、個数の等式が従う。射影 $(g,h)\mapsto g$ と $(g,h)\mapsto h$ は、$F=G\times H$ に対する恒等写像の成分なので準同型であり、prop-ghom-monotone から最後の不等式が従う。$\square$

段 1（分解）．任意の有限グラフ $F,G$ について
$$ \hom(F,G)=\sum_{P}\mathrm{inj}(F/P,G) $$
が成り立つ。和は $F$ の許される分割 $P$ 全体にわたる。準同型 $f\colon F\to G$ について、$f$ の空でない逆像 $f^{-1}(x)$ の全体を $P_f$ とすると、各ブロックは独立集合なので $P_f$ は許される分割であり、$f$ はブロック $B$ に $f(B)$ の元を対応させる単射 $\bar f\colon V(F/P_f)\to V(G)$ を定める。$F/P_f$ の辺 $BB'$ には $u\in B$、$v\in B'$ となる辺 $uv$ があり、$\bar f(B)\bar f(B')=f(u)f(v)\in E(G)$ なので、$\bar f$ は単射な準同型である。逆に許される分割 $P$ と単射な準同型 $g\colon F/P\to G$ が与えられたとき、頂点をそのブロックへ写す写像と $g$ の合成 $f$ は準同型である。$F$ の辺 $uv$ の端点は、ブロックが独立集合なので異なるブロックに属し、それらのブロックは $F/P$ で隣接するからである。$g$ が単射なので $P_f=P$、$\bar f=g$ となる。2 つの対応は互いに逆である。
段 2（帰納法）．頂点の個数 $n$ についての帰納法で、「$n$ 頂点以下のすべての $F$ で $\mathrm{inj}(F,G)=\mathrm{inj}(F,H)$」を示す。$F$ を $n$ 頂点とする。各ブロックが 1 点の分割は許される分割で、$F/P$ は $F$ と同型である。ほかの許される分割では $F/P$ の頂点は $n$ 個より少ない。段 1 から
$$ \mathrm{inj}(F,G)=\hom(F,G)-\sum_{P\text{：1 点でないブロックを含む}}\mathrm{inj}(F/P,G) $$
であり、右辺は仮定と帰納法の仮定により $G$ を $H$ に置き換えても変わらない（$n=0$ では和は空である）。
段 3（同型）．段 2 により $\mathrm{inj}(G,H)=\mathrm{inj}(G,G)\ge1$（恒等写像）と $\mathrm{inj}(H,G)=\mathrm{inj}(H,H)\ge1$ なので、単射な準同型 $\varphi\colon G\to H$ と $\psi\colon H\to G$ がある。lem-ghom-equivalent-cores の証明の後半と同じく、頂点の個数と辺の本数が等しいので、$\varphi$ は頂点と辺の両方で全単射になり、同型である。$\square$