Cayleyグラフ

1：$L_\gamma$ は $L_{\gamma^{-1}}$ を逆写像とする全単射である。$(\gamma g)^{-1}(\gamma h)=g^{-1}h$ なので、$g,h$ が隣接することと $\gamma g,\gamma h$ が隣接することは同値であり、$L_\gamma$ は自己同型である。$L_{\gamma\delta}=L_\gamma\circ L_\delta$ で、$L_\gamma=\mathrm{id}$ なら $\gamma=L_\gamma(1)=1$ である。
2：$L_\gamma(g)=h$ は $\gamma=hg^{-1}$ と同値である。
3：$\alpha$ は全単射で、$\alpha(g)^{-1}\alpha(h)=\alpha(g^{-1}h)$ である。$\alpha(S)=S$ なので $g^{-1}h\in S$ と $\alpha(g^{-1}h)\in S$ は同値であり、$\alpha$ は隣接関係を保つ。$\alpha(1)=1$ である。$\square$

$L_\gamma(gs)=\gamma gs=L_\gamma(g)s$ である。逆に $F$ が条件を満たすとし、$\gamma:=F(1)$ とおく。$S^{-1}=S$ なので、$\Gamma$ の元は $S$ の元の有限個の積 $s_1\cdots s_k$（$k=0$ は $1$）として書ける（部分群 の記事の命題「生成される部分群の元の記述」）。$k$ についての帰納法で $F(s_1\cdots s_k)=\gamma s_1\cdots s_k$ を示す。$k=0$ は $\gamma$ の定義である。$k-1$ まで正しければ $F(s_1\cdots s_{k-1}s_k)=F(s_1\cdots s_{k-1})s_k=\gamma s_1\cdots s_{k-1}s_k$ である。よって $F=L_\gamma$ である。$\square$

$g$ から $h$ への長さ $k$ の歩道 $g=g_0,g_1,\dots,g_k=h$ があると、$s_i:=g_{i-1}^{-1}g_i\in S$ について $g^{-1}h=s_1\cdots s_k$ である。逆に $g^{-1}h=s_1\cdots s_k$ なら $g,\ gs_1,\ gs_1s_2,\ \dots,\ gs_1\cdots s_k=h$ は長さ $k$ の歩道である。よって $g$ から $h$ への歩道の長さの最小値は $\lvert g^{-1}h\rvert_S$ に等しい。歩道の長さの最小値は道の長さの最小値に等しい（距離(グラフ) の記事の補題「歩道からの道の取り出し」）ので、これはグラフの距離である。グラフは連結なので、同記事の命題「距離空間の公理」により $d_S$ は距離関数である。不変性は $(\gamma g)^{-1}(\gamma h)=g^{-1}h$ による。$\square$

$S$ は有限なので $C$ は有限である。$k:=d_S(g,h)$ とし $g^{-1}h=s_1\cdots s_k$ と書く。各 $s_i$ は $T$ の元 $C$ 個以下の積なので、$g^{-1}h$ は $T$ の元 $Ck$ 個以下の積であり、$d_T(g,h)\le Ck$ である。$S$ と $T$ を入れ替えた不等式と合わせ、2 つの定数の大きい方を $C'$ とすればよい（$C'\ge1$ は $\Gamma\neq\{1\}$ なら $C\ge1$ から、$\Gamma=\{1\}$ なら距離がすべて $0$ であることから成り立つ）。$\square$

作用が自由かつ推移的なので、各頂点 $v$ について $hv_0=v$ となる $h\in H$ がただ 1 つあり、$\Phi$ は全単射である。単純グラフにループはないので $v_0$ は $v_0$ と隣接せず、$1\notin S$ である。$s\in S$ なら、自己同型 $s^{-1}$ を $sv_0$ と $v_0$ の辺に施すと $v_0$ と $s^{-1}v_0$ が隣接するので、$s^{-1}\in S$ である。
$h,h'\in H$ について
$$ h^{-1}h'\in S\iff h^{-1}h'v_0\text{ と }v_0\text{ が隣接}\iff h'v_0\text{ と }hv_0\text{ が隣接} $$
である。2 つ目の同値は、自己同型 $h$（またはその逆）を施すと隣接関係が保たれることによる。左辺は $\operatorname{Cay}(H,S)$ で $h$ と $h'$ が隣接すること、右辺は $X$ で $\Phi(h)$ と $\Phi(h')$ が隣接することなので、$\Phi$ は同型である。逆向きは thm-cg-left の 2 による。$\square$

頂点推移的であることは Petersenグラフ の記事の定理「自己同型群」による。Petersen グラフ $P$ は 10 頂点の 3-正則グラフで、内周（最短の閉路の長さ）は $5$ である（同記事の命題「共通の隣接頂点と内周」）。
$P\cong\operatorname{Cay}(\Gamma,S)$ とすると $\lvert\Gamma\rvert=10$、$\lvert S\rvert=3$ である。まず、$S$ の元の積 $s_1s_2\cdots s_k=1$（$k=3$ または $4$）で $s_{i+1}\neq s_i^{-1}$（$1\le i\le k-1$）を満たすものはないことを示す。そのような積があると、頂点の列 $g_i:=s_1\cdots s_i$（$g_0=g_k=1$）は $g_{i+1}\neq g_{i-1}$ を満たす閉じた歩道になる。$g_i=g_j$（$i< j$）となる組のうち $j-i$ が最小のものをとると、$j-i=1$ はループになり、$j-i=2$ は $g_{i+2}=g_i$ となるので起こらず、$g_i,\dots,g_j$ は長さ $3$ 以上 $k$ 以下の閉路になって、内周が $5$ であることに反する。
$\lvert S\rvert=3$ は奇数で、$s\ne s^{-1}$ となる元は $\{s,s^{-1}\}$ の組で現れるので、$S$ は位数 $2$ の元 $a$ を含む。

$(Av_j)_k=\sum_{s\in S}(v_j)_{k+s}=\sum_{s\in S}\omega^{j(k+s)}=\lambda_j\,\omega^{jk}$ なので $Av_j=\lambda_jv_j$ である。$v_0,\dots,v_{n-1}$ を並べた行列は、相異なる $1,\omega,\dots,\omega^{n-1}$ についての Vandermonde 行列なので正則であり、$v_j$ は基底をなす。よって $A$ の固有値は重複を込めて $\lambda_0,\dots,\lambda_{n-1}$ である。$-S=S$ なので $s$ と $-s$ の項をまとめると虚部が消え、$\lambda_j$ は余弦の和になる。$\square$