数理論理学・集合論の問題

方針. 自己同型は「$E(x,y)$ となる $y$ の個数」（次数）を保つ。次数で元の行き先を絞り、残った自由度を数える。

次数を調べる. 各頂点の隣接する頂点は
- $1$: $2,3,4,5$（次数 $4$）
- $5$: $1,6$（次数 $2$）
- $2,3,4,6$: それぞれ $1$ つだけ（次数 $1$）。$2,3,4$ の相手は $1$、$6$ の相手は $5$

行き先を絞る. 自己同型 $\sigma$ は辺を辺に、辺でない組を辺でない組に移すので、$a$ の次数と $\sigma (a)$ の次数は等しい。
- 次数 $4$ の頂点は $1$ だけなので $\sigma (1)=1$。
- 次数 $2$ の頂点は $5$ だけなので $\sigma (5)=5$。
- 次数 $1$ の頂点 $2,3,4,6$ のうち、$6$ だけが「次数 $2$ の頂点と隣接する」という性質をもつ。$E(6,5)$ から $E(\sigma (6),\sigma (5))=E(\sigma (6),5)$ なので $\sigma (6)\in \{1,6\}$ であり、$\sigma (1)=1$ だから $\sigma (6)=6$。
- 残る $2,3,4$ は $\{2,3,4\}$ の中で並べ替えられる。

数える. 逆に、$1,5,6$ を固定し $2,3,4$ を任意に並べ替える $\sigma$ は、辺 $\{1,2\},\{1,3\},\{1,4\}$ をこの 3 本の中で入れ替え、辺 $\{1,5\},\{5,6\}$ をそのまま保つので、自己同型である。$2,3,4$ の並べ替えは $3!=6$ 通り。

したがって自己同型の個数は $6$ である。

グラフの辺は $1\text{-}2,1\text{-}3,1\text{-}4,1\text{-}5,5\text{-}6$。次数は $\mathrm{deg}1=4,\mathrm{deg}5=2,\mathrm{deg}2=\mathrm{deg}3=\mathrm{deg}4=\mathrm{deg}6=1$。

自己同型は次数を保つので、次数 4 の頂点 1 は固定、次数 2 の頂点 5 も固定される。次数 1 の頂点は $\{2,3,4,6\}$ で、$6$ は固定された頂点 5 の隣（かつ 1 の隣でない）、$2,3,4$ は頂点 1 の隣である。隣接関係を保つため、$6$ は $5$ の次数 1 の隣接頂点として固定され、$\{2,3,4\}$ は $\{2,3,4\}$ に写る。

逆に、$2,3,4$ の任意の置換（$1,5,6$ は固定）は辺をすべて保つ（$1$ と $2,3,4$ の辺の集合が入れ替わるだけ）。よって自己同型群は $S_3$ に同型で、個数は $3!=6$。

検算: 軌道・安定部分群の考え方では、頂点 2 の軌道は $\{2,3,4\}$（大きさ 3）、2 の安定部分群は 3, 4 を入れ替える 2 元。$3\times 2=6$ で一致する。