Petersenグラフ

表の 10 個の 2 元部分集合は相異なり、10 個すべてを尽くすので、対応は頂点の全単射である。$P'$ の 15 本の辺の端点の組が $P$ で交わらないことを確かめる。外側の辺は $12$–$34$、$34$–$15$、$15$–$23$、$23$–$45$、$45$–$12$、スポークは $12$–$35$、$34$–$25$、$15$–$24$、$23$–$14$、$45$–$13$、内側の辺 $u_0u_2,u_1u_3,u_2u_4,u_3u_0,u_4u_1$ は $35$–$24$、$25$–$14$、$24$–$13$、$14$–$35$、$13$–$25$ で、どれも交わらない。よって対応は $P'$ の辺を $P$ の辺に写す。辺の本数はどちらも $15$ なので、$P$ の辺はすべて $P'$ の辺の像であり、対応は同型写像である。$\square$

1．隣接する $ab$ と $cd$ は交わらないので、$a,b,c,d$ は相異なる。両方と交わらない 2 元部分集合は、残りの 1 元 $\{e\}$ に含まれなければならないが、そのようなものはない。
2．隣接しない相異なる 2 頂点は交わるので、$ab$ と $ac$（$b\ne c$）と書ける。両方と交わらない 2 元部分集合は $\{1,\dots,5\}\setminus\{a,b,c\}$ に含まれ、この集合はちょうど 2 元なので、それ自身がただ 1 つの共通の隣接頂点である。
3．1 から三角形はない。長さ $4$ の閉路 $xyzw$ があれば、三角形がないので $x$ と $z$ は隣接せず、$y$ と $w$ という 2 つの共通の隣接頂点をもつことになり、2 に反する。一方、外側の五角形は長さ $5$ の閉路である。直径については、隣接しない 2 頂点が 2 により距離 $2$ で結ばれることから従う。$\square$

頂点 $x$ を固定し、その隣接頂点を $a,b,c$ とする。$a$ の $x$ 以外の隣接頂点を $a_1,a_2$、同様に $b_1,b_2$、$c_1,c_2$ とする。
段 1（10 頂点が相異なる）． $a_i$ は $x$ でない（単純グラフなので $x$ は $a$ に 1 回しか隣接しない）。$a_i\in\{b,c\}$ なら $x,a,a_i$ が三角形をなす。$a_i=b_j$ なら $x\,a\,a_i\,b\,x$ が長さ $4$ の閉路になる。他の組も同様なので、$x,a,b,c,a_1,a_2,b_1,b_2,c_1,c_2$ は相異なる。これで 1 が示された。
段 2（2 段目の辺）． 頂点がちょうど $10$ 個なら、これらが全頂点である。$x,a,b,c$ はすでに次数 $3$ をもつので、$a_1$ の残り 2 本の辺は 2 段目の頂点へ行く。$a_1$ と $a_2$ は隣接しない（$a$ と三角形をなす）。$a_1$ が $b_1$ と $b_2$ の両方に隣接すると $a_1b_1bb_2a_1$ が長さ $4$ の閉路になる。よって $a_1$ は $b_1,b_2$ のちょうど一方と、$c_1,c_2$ のちょうど一方に隣接する。2 段目のどの頂点についても同じことが成り立つ。
段 3（名前の付け方で辺が決まる）． 必要なら $b_1,b_2$ の名前を入れ替えて $a_1\sim b_1$ とする。$b_1$ の $a$ 側の隣接頂点は $a_1$ だけなので $a_2\not\sim b_1$、よって $a_2\sim b_2$ である。同様に $c_1,c_2$ の名前を選んで $a_1\sim c_1$、$a_2\sim c_2$ とする。$b_1\sim c_1$ なら $a_1b_1c_1$ が三角形になるので $b_1\sim c_2$、したがって $b_2\sim c_1$ である。これで $G$ の 15 本の辺
$$ xa,\ xb,\ xc,\ aa_1,\ aa_2,\ bb_1,\ bb_2,\ cc_1,\ cc_2,\ a_1b_1,\ a_2b_2,\ a_1c_1,\ a_2c_2,\ b_1c_2,\ b_2c_1 $$
がすべて決まった。
段 4（同型と個数）． $P$ は 3-正則で内周 $5$（prop-pg-srg）の 10 頂点のグラフなので、$P$ にも同じ名前付けができる。両方の名前付けで同じ名前の頂点を対応させると、辺の一覧が同じなので同型写像になる。逆に、同型写像 $\varphi\colon G\to P$ は、$\varphi(x)$（$10$ 通り）、$\varphi(a),\varphi(b),\varphi(c)$ の並び（$3!=6$ 通り）、$\varphi(a_1)$（$\varphi(a)$ の $\varphi(x)$ 以外の隣接頂点で $2$ 通り）を決めると、残りの像がすべて決まる。実際、$\varphi(a_2)$ は $\varphi(a)$ の残りの隣接頂点、$\varphi(b_1)$ は $\varphi(b)$ の隣接頂点のうち $\varphi(a_1)$ に隣接するただ 1 つの頂点（段 2）であり、以下同様である。よって同型写像は $10\cdot6\cdot2=120$ 個以下である。$\square$

$\sigma$ は 2 元部分集合を 2 元部分集合に写し、交わらないという関係を保つので、$P$ の自己同型を定める。対応 $\sigma\mapsto(\text{その自己同型})$ は群の準同型である。単射であることを示す。$\sigma$ がすべての頂点を固定するとし、$a\in\{1,\dots,5\}$ と $b\ne c$（$b,c\ne a$）をとる。$\sigma(\{a,b\})=\{a,b\}$ と $\sigma(\{a,c\})=\{a,c\}$ から $\sigma(a)\in\{a,b\}\cap\{a,c\}=\{a\}$ である。よって $\sigma$ は恒等置換である。
したがって $\operatorname{Aut}P$ は位数 $120$ の部分群を含む。一方、thm-pg-moore の 2 を $G=P$ に当てると $P$ から $P$ への同型写像は $120$ 個以下である。よって $S_5\cong\operatorname{Aut}P$ である。
推移性：交わらない 2 元部分集合の順序対 $(ab,cd)$ と $(a'b',c'd')$ が与えられたとき、残りの元を $e,e'$ として $a\mapsto a'$、$b\mapsto b'$、$c\mapsto c'$、$d\mapsto d'$、$e\mapsto e'$ とする置換は前者を後者に写す。頂点の推移性はとくにこの場合である。$\square$

Hamilton 閉路 $C=w_0w_1\cdots w_9w_0$ があるとして矛盾を導く（添字は $10$ を法とする）。各頂点は $C$ の 2 本の辺に接続し、次数は $3$ なので、$C$ に含まれない辺（弦 と呼ぶ）は各頂点にちょうど 1 本ずつあり、弦は全部で $5$ 本である。
弦 $w_iw_j$ について、$C$ の上での $w_i$ と $w_j$ の距離 $d$（$|i-j|$ と $10-|i-j|$ の小さい方）を考える。弦は $C$ の辺でなく $P$ は単純グラフなので $d\ge2$ であり、弦と $C$ の短い方の弧は長さ $d+1$ の閉路をなす。$P$ の内周は $5$（prop-pg-srg）なので $d\ge4$、すなわち $d\in\{4,5\}$ である。
場合 1：すべての弦で $d=5$． 弦 $w_0w_5$ と $w_1w_6$ があり、$w_0w_1w_6w_5w_0$ は長さ $4$ の閉路になる。矛盾である。
場合 2：$d=4$ の弦がある． 添字をずらして、それが $w_0w_4$ であるとしてよい。$w_5$ の弦の相手は $d\in\{4,5\}$ から $w_1,w_9,w_0$ のどれかで、$w_0$ はすでに $w_4$ と結ばれている。$w_5w_1$ なら $w_0w_1w_5w_4w_0$ が長さ $4$ の閉路になるので、弦は $w_5w_9$ である。
$w_1$ の弦の相手は $w_5,w_6,w_7$ のどれかで、$w_5$ は使われている。

• $w_1w_6$ のとき：$w_7$ の弦の相手は $w_1,w_2,w_3$ のどれかで、$w_1$ は使われている。$w_7w_2$ なら $w_1w_2w_7w_6w_1$ が長さ $4$ の閉路になる。$w_7w_3$ なら残る $w_2,w_8$ が弦 $w_2w_8$ で結ばれ、$w_2w_3w_7w_8w_2$ が長さ $4$ の閉路になる。
• $w_1w_7$ のとき：$w_3$ の弦の相手は $w_7,w_8,w_9$ のどれかで、$w_7,w_9$ は使われているので $w_3w_8$ であり、残る $w_2,w_6$ が弦 $w_2w_6$ で結ばれる。$w_1w_2w_6w_7w_1$ は長さ $4$ の閉路になる。
  どの場合も内周が $5$ であることに反する。$\square$

thm-pg-automorphism により $P$ は頂点推移的なので、$x=v_0$ の場合を示せばよい。prop-pg-drawing の辺の一覧から
$$ v_1\,v_2\,v_3\,v_4\,u_4\,u_2\,u_0\,u_3\,u_1\,v_1 $$
の各隣接対は辺であり（外側の辺 $v_1v_2,v_2v_3,v_3v_4$、スポーク $v_4u_4,u_1v_1$、内側の辺 $u_4u_2,u_2u_0,u_0u_3,u_3u_1$）、$v_0$ 以外の 9 頂点をちょうど 1 回ずつ通る。$\square$

外側の五角形は長さ $5$ の奇閉路なので 2 色では塗れず、$\chi(P)\ge3$ である。次の 3 つの組に色 $1,2,3$ を塗る。
$$ \{12,13,14,15\},\qquad\{23,24,25\},\qquad\{34,35,45\}. $$
最初の組はどれも $1$ を含み、2 番目の組はどれも $2$ を含む。3 番目の組は 3 元集合 $\{3,4,5\}$ の 2 元部分集合なので、どの 2 つも交わる。よって各組の中の 2 頂点は交わり、隣接しない。これは 3-頂点彩色であり、$\chi(P)=3$ である。$\square$

$P$ は 3-正則で、$M$ は各頂点にちょうど 1 本の辺をもつので、$P-M$ は 2-正則である。2-正則な有限グラフの各連結成分は閉路であり（閉路 の記事の命題「連結で次数がすべて 2 のグラフ」）、各閉路の長さは内周 $5$ 以上である（prop-pg-srg）。頂点は $10$ 個なので、$P-M$ は長さ $10$ の閉路 1 つか、長さ $5$ の閉路 2 つである。前者は $P$ の Hamilton 閉路になり、thm-pg-nonhamiltonian に反する。$\square$

3 色の辺彩色があるとして矛盾を導く。各頂点には 3 本の辺が集まり、それらは相異なる色なので、各頂点に 3 色がちょうど 1 回ずつ現れる。したがって各色の辺の集合 $M_1,M_2,M_3$ は完全マッチングである。$P-M_3$ の辺は色 $1,2$ だけで塗られ、各頂点で 2 色が 1 本ずつ現れるので、$P-M_3$ の各閉路の辺は色 $1$ と色 $2$ が交互に並び、閉路の長さは偶数である。ところが lem-pg-two-factor により $P-M_3$ は長さ $5$ の閉路 2 つからなる。これは矛盾である。
よって $\chi'(P)\ge4$ であり、Vizingの定理 の定理「Vizing の定理」から $\chi'(P)\le\Delta(P)+1=4$ である。$\square$