因课程原因要详细分析如下定理，其证明巨长无比，但说实话，这个证明的本质困难不太多，只是看着莫名的复杂。也不知道这证明到底咋想的，暂且记在这里吧。
(Tutte) 令 \(\Gamma\) 为一个连通 \(3\) 度弧传递图，则存在正整数 \(s\leq5\)，使得 \(\Gamma\) 是 \(s\)-弧正则的.
引理 1
假设 \(\Gamma\) 是一个连通 \(3\) 度弧传递图，如果 \(\Gamma\) 是 \(s\)-弧传递的，但不是 \((s+1)\)-弧传递的，那么 \(\mathrm{Aut}(\Gamma)\) 在 \(\Gamma\) 的 \(s\)-弧集合上的作用是正则的.
这个东西其实很简单，且记 \(A=\mathrm{Aut}(\Gamma)\)，只要注意到，任给 \(v_0-v_1-\cdots-v_s\) 为 \(s\)-弧，它的稳定子 \(A_{v_0\cdots v_s}\) 必然固定 \(v_s\) 仅有的三个邻居，不然这个图就是 \((s+1)\)-弧传递的，矛盾. 这样，记 \(v_s\) 不同于 \(v_{s-1}\) 的某个邻居是 \(v_{s+1}\)，必有 \(A_{v_0\cdots v_s} \leq A_{v_0\cdots v_s v_{s+1}}\)，进而这俩只能相等，因为后者显然是前者的子群. 那么同理，反着取一条弧 \(A_{v_1\cdots v_{s+1}}\) 也只能是 \(A_{v_0\cdots v_s v_{s+1}}\)，所以事实上这几个都一样，总之，我们得到了：
\[ A_{v_0\cdots v_s}=A_{v_1\cdots v_{s+1}} \]
这是一个很强的结论，这意味着 \(s\)-弧的稳定子可以“流动”. 现在，任给 \(u \in \Gamma\)，据连通性，总能找到 \(v_s,u\) 之间的一条路 \(v_s,v_{s+1},\cdots,v_{s+k}=u\)，一个自然的考虑是：
\[ A_{v_0\cdots v_s}=A_{v_1\cdots v_{s+1}}=\cdots=A_{v_{k}\cdots v_{s+k}}\leq A_{u} \]
也就是说 \(A_{v_0\cdots v_s}\) 固定了任意的点 \(u\)，那它只能是 \(1\)，即相应的作用是正则的.
然而这个考虑有一个问题：\(v_{s+1}\) 未必不等于 \(v_{s-1}\)，要修正这一点，利用图是三度的，总能找到这样一条弧：
\[ v_0-v_1-\cdots-v_s-u_{s+1}-\cdots-u_{2s - 1} \]
使得 \(u_{s+1}\neq v_{s+1}\)，这样，先将原来那条弧搬到右边去，再同理考虑，就有：
\[ A_{v_0\cdots v_s}=A_{v_s u_{s+1}\cdots u_{2s-1}}=A_{v_{k}\cdots v_{s+k}}\leq A_{u} \]
至此我们的证明就严格了.
引理 2
假设 \(\Gamma=(V,E)\) 是一个连通 \(3\) 度 \(s\)-弧传递但非 \((s+1)\)-弧传递的图，其中 \(s \geq 2\). 任取 \(\{u,v\} \in E(\Gamma)\) 以及 \(y \in V(\Gamma)\)，如果 \(d(u,y)\) 或者 \(d(v,y)\) 小于 \(\frac{s+1}{2}\)，那么 \(Z(\mathrm{Aut}(\Gamma)_{uv}) \leq \mathrm{Aut}(\Gamma)_y\).
还是记 \(A=\mathrm{Aut}(\Gamma)\)，首先，用引理 1，\(A\) 的阶就是 \(s\)-弧集合那么多，也就是 \(|V|\times 3 \times 2^{s-1}\)，这是因为，要想任取一个 \(s\)-弧，首先任取一个点，因为是三度图，第一步有 \(3\) 种选择，剩下 \(s-1\) 步有 \(2\) 种选择. 同理，\(A_{uv}\) 的前两步被定死，所以 \(|A_{u v}|=2^{s-1}\) 是一个 \(2\)-群. 据 Class Formula，\(p\)-群的中心模 \(p\) 余 \(0\)，所以 \(|Z(A_{u v})| \geq 2\).
下面且记 \(u_0=u,u_1=v\)，然后我们取 \(\Gamma\) 的任意一条 \(s\)-弧 \(u_0-u_1-\cdots-u_s\)，要证原命题，只要证对任意 \(k \leq \frac{s-1}{2}\)，都有 \(Z(A_{u_0 u_1}) \leq A_{u_0 u_1 \cdots u_k} \leq A_{u_k}\).
接下来的论证有点类似于 \(s\)-弧传递与围长 \(g\) 的关系，这个大概是说考虑图上的 \(g\)-圈，这个圈上的 \(s\)-弧，首尾距离必须是 \(s\) 而非 \(g-s\)，否则就会找到更小的圈，与 \(g\) 是围长矛盾.
回到原命题，且记 \(Z=Z(A_{u_0 u_1})\)，由于 \(A_{u_0 \cdots u_s}=1\)，并且
\[ \begin{aligned} &A_{u_0 u_1} \geq Z \geq 1 \\ &A_{u_0 u_1} \geq A_{u_0 u_1 u_2} \geq \cdots \geq A_{u_0 \cdots u_s}=1 \end{aligned} \]
所以一定存在某个 \(1 \leq t < s\) 使得，\(Z \leq A_{u_0 \cdots u_t}\) 但是 \(Z \nsubseteq A_{u_0 \cdots u_t u_{t+1}}\). 于是，我们可以取一个 \(g \in Z \setminus A_{u_0 \cdots u_t u_{t+1}}\)，这样 \(g\) 跟 \(A_{u_0 u_1}\) 交换，进而成立：
\[ A_{u_0 u_1 ... u_{s-1}} = A^g_{u_0 u_1 ... u_{s-1}}=A_{u_0^g u_1^g ... u_{s-1}^g} \]
且由 \(Z \leq A_{u_0 \cdots u_t}\)，我们知道 \(u_i^g=u_i, i \leq t\)，又因为 \(g\) 是双射，\(u_{t+1}^g\) 必不等于 \(u_{t+1}\)，\(u_t\) 必不等于 \(u_{t+2}^g\). 也就是说，我们能找到这样一条弧：
\[ u_{s-1}-u_{s-2}-\cdots-u_t-u_{t+1}^{g}-\cdots u_{s-1}^g \]
这条弧长为 \(2(s-t-1)\)，另一方面，由刚才的式子可以看出，\(A_{u_0 u_1 ... u_{s-1}}\) 固定这条弧，因而是这条弧稳定子的子群，而 \(A_{u_0 u_1 ... u_{s-1}}\) 是 \(2\) 阶群，所以这条 \(2(s-t-1)\) 弧的稳定子是非平凡的. 根据引理 1，任何长度大于等于 \(s\) 的弧，它的稳定子肯定是平凡的，这表明 \(2(s - t -1) \leq s-1\)，也就是 \(t \geq \frac{s-1}{2}\)，可见对任意的 \(k \leq \frac{s-1}{2} \leq t\)，原命题确实成立.
定理证明
设 \(\Gamma=(V,E)\) 是一个连通 \(3\) 度 \(s\)-弧传递但非 \((s+1)\)-弧传递的图，我们将证明，若 \(s\geq4\)，则必有 \(s \leq 5\)，因而原命题成立. 下面还是记 \(A=\mathrm{Aut}(\Gamma)\).
首先，令 \(m=\left[\frac s 2\right]-1\)，取 \((u_0,u_1,u_2,...,u_{3m})\) 为一条 \(3m\)-弧，我们将大量利用引理 2，导出 \(m\) 与 \(s\) 的关系，限制 \(s\) 的大小. 现在，取 \(H_1=Z(A_{u_{m-1}u_m}),H_2=Z(A_{u_{2m}{u_2m+1}})\)，令：
\[ H=[H_1,H_2]:=\langle a^{-1}b^{-1}ab:a \in H_1, b \in H_2\rangle \]
我们将证明两点：
- \(H\) 固定了整个 \((u_0,u_1,u_2,...,u_{3m})\).
- \(H\geq 1\)，即 \(H\) 是非平凡的.
基于这两点，以及引理 1，我们就会得到：
\[ 3\left(\left[\frac s 2\right]-1\right)\leq s-1. \]
因而当 \(s\) 为偶数时，\(s\leq 4\)；当 \(s\) 为奇数时，\(s \leq 7\)；证到这里，我们只需要排除 \(s=7\) 的情况即可，下面我们一个一个来看.
\(H \leq A_{u_0 u_1 \cdots u_{3m}}\)
首先由引理 2，\(H_1\) 固定 \(u_0,\cdots,u_{2m}\)，\(H_2\) 固定 \(u_m,\cdots,u_{3m}\)，进而 \(H\) 固定中间的 \(u_m,\cdots,u_{2m}\). 现在，任给 \(0\leq i \leq m\)，我们要证 \(H\) 固定 \(u_{i}\)，也就是证任给 \(a \in H_1, b \in H_2\)，成立：
\[ a^{-1}b^{-1} a b \in A_{u_i} \]
而 \(a^{-1}\) 本就固定 \(u_i\)，故只要证：
\[ \begin{aligned} &b^{-1} a b \in A_{u_i} \iff u_i^{b^{-1} a b}=u_i \iff u_i^{b^{-1}}=u_i^{b^{-1} a^{-1}} \end{aligned} \]
也就是只要证 \(a^{-1}\) 也固定 \(u_i^{b^{-1}}\). 事实上，因为 \(b^{-1}\) 固定 \(u_m\)，必有
\[ d(u_m,u_i^{b^{-1}})=d(u_m,u_i) \leq m \]
所以引理 2 对 \(u_i^{b^{-1}}\) 同样适用，即 \(a^{-1}\) 确实固定 \(u_i^{b^{-1}}\). 这样，我们就证明了 \(H\) 也固定 \(u_0,\cdots,u_{m}\)，剩下的部分是同理的.
\(H \geq 1\)
首先，由引理 \(2\) 类似的讨论，我们知道 \(H_1,H_2\) 都是非平凡 \(2\)-群的中心，因而是非平凡的. 下面用反证法. 假设 \(H=1\)，这就是说 \(H_1,H_2\) 交换.
取 \(u_{-1} \in \Gamma(u_0) \setminus \{u_1\},u_{3m+1} \in \Gamma(u_{3m}) \setminus \{u_{3m-1}\}\)，注意 \(m\) 取得比 \(\left[\frac s 2\right]\) 还小，由引理 2，\(H_1\) 事实上也固定 \(u_{-1}\)，同理 \(H_2\) 固定 \(u_{3m+1}\). 考虑弧：
\[ P=u_{-1}-u_0-\cdots-u_{2m+1} \]
则 \(P\) 是 \((2m+2)\)-弧. 现在，我们分 \(s\) 的奇偶性讨论这条弧.
\(s\) 为偶数
此时 \(2m+2 = s\). 这样，若 \(H_1\) 固定 \(u_{2m+1}\)，\(H_1\) 就固定了 \(P\) 这条 \(s\)-弧，由引理 1，\(H_1\) 平凡，矛盾. 因此，必存在 \(a \in H_1\) 使 \(u_{2m+1}^a\neq u_{2m+1}\)，这样，我们可以找到另一条 \(s\)-弧：
\[ Q=u_{3m+1}-u_{3m}-\cdots-u_{2m+1}-u_{2m}-u_{2m+1}^a-\cdots-u_{3m}^a-u_{3m+1}^a \]
由于 \(H_1,H_2\) 可交换，\(H_2^a=H_2\)，这就是说 \(H_2\) 必固定 \(Q\)，进而平凡，矛盾.
\(s\) 为奇数
此时 \(2m+2 = s-1\). 类似分析，若 \(H_1\) 固定 \(u_{2m+1}\)，那么取 \(u_{-2} \in \Gamma(u_{-1}) \setminus \{u_0\}\)，考虑另一 \((s-1)\)-弧：
\[ W=u_{2m}-\cdots-u_{0}-u_{-1}-u_{-2} \]
取 \(\alpha \in A\) 使得 \(P^\alpha=W\)，不难验证 \(\alpha(u_j)=u_{2m-1-j}\)，可见 \(A_{u_{2m-1}u_{2m}}^\alpha=A_{u_{2m}u_{2m-1}}\)，因而 \(H_1^\alpha=H_1\)（中心是特征子群），可见 \(H_1\) 固定 \(u_{-2}-\cdots-u_{2m+1}\) 这一 \(s\)-弧，矛盾.
因此，必存在 \(a \in H_1\) 使 \(u_{2m+1}^a\neq u_{2m+1}\)，同理，我们可以找到另一条 \((s-1)\)-弧：
\[ Q=u_{3m+1}-u_{3m}-\cdots-u_{2m+1}-u_{2m}-u_{2m+1}^a-\cdots-u_{3m}^a-u_{3m+1}^a \]
且 \(H_2\) 必固定 \(Q\). 考虑另一 \((s-1)\)-弧：
\[ R=u_{-1}-u_{0}-\cdots-u_{2m+1} \]
取 \(\beta \in A\) 使得 \(Q^\beta=R\)，不难验证 \((u_{2m},u_{2m+1})^\beta=(u_m,u_{m-1})\)，因而 \(H_1=H_2^\beta\)，进而 \(H_1\) 固定 \(R\)，但是 \(a\) 不固定 \(u_{2m+1}\)，矛盾.
讨论 \(s=7\)
至此，我们只需要讨论 \(s=7\) 的情况是不成立的. 反证法，设 \(s=7\)，取
\[ W=v_0-v_1-\cdots-v_7 \]
为一条 \(7\)-弧. 设 \(v_8,v_8'\) 为 \(v_7\) 不同于 \(v_6\) 的邻居，取 \(g,h \in A\) 使得：
\[ \begin{aligned} W^g&=v_1-v_2-\cdots-v_7-v_8 \\ W^h&=v_1-v_2-\cdots-v_7-v_8' \end{aligned} \]
取 \(x_0 = g h^{-1}\)，那么 \(x_0\) 固定 \(v_0,\cdots,v_6\)，但是 \((v_8')^{h^{-1}}=v_7\) 说明 \(v_8^{h^{-1}}\neq v_7\)，即 \(x_0\) 不固定 \(v_7\). 这样，\(x_0\) 是 \(A_{v_0\cdots v_6}\) 的非平凡元，由引理 2 的讨论，\(\lvert A_{v_0\cdots v_6} \rvert=2\)，故 \(x_0\) 必为二阶元.
记 \(v_{-i}=v_0^{g^{-i}}\)，令 \(x_i= g^{i} x_0 g^{-i}\)，其中 \(1\leq i \leq 5\). 易见诸 \(x_i\) 均为二阶元，且固定
\[ W_i = v_{-i}-\cdots-v_0-\cdots-v_{6-i} \]
我们将证明：\(x_0\) 会稳定这样一个 \(7\)-弧：
\[ v_3^{x_5}-v_2^{x_5}-v_1-v_2-\cdots-v_6 \]
因而 \(x_0\) 平凡，导致矛盾. 要证明这一点，注意到 \(x_0\) 已经固定 \(v_2,v_3\)，那么：
\[ v_k^{x_5x_0}=v_k^{x_5} \iff v_k^{x_5x_0}=v_k^{x_0x_5}, \]
即我们只要证 \([x_0,x_5]\) 固定 \(v_k\)，其中 \(k=2,3\). 为研究这一点，我们需要逐个考虑 \([x_0,x_i]\).
\([x_i,x_{i+1}]=1\)，即 \(x_i,x_{i+1}\) 交换
首先，\(x_1\) 必交换 \(v_6\) 和 \(v_6^{x_1}\)，而 \(x_0\) 必固定 \(v_6\) 以及 \(v_6^{x_1}\)，这就是说，\(x_1 x_0 x_1\) 必固定
\[ v_0-v_1-\cdots-v_6 \]
且由 \(x_1\) 固定 \(v_{-1}\)，但 \(x_0\) 不固定 \(v_{-1}\)， \(x_1 x_0 x_1\) 必为 \(A_{v_0\cdots v_6}\) 的非平凡元，也就是 \(x_1 x_0 x_1 = x_0\)，即 \([x_0,x_1]=1\). 进而 \([x_i,x_{i+1}]=g^i[x_0,x_1]g^{-i}=1\).
记 \(X_i=\langle x_0,\cdots,x_i \rangle\)，则 \(\lvert X_i \rvert = 2^{i+1}\)
显然 \(\lvert X_5 \rvert \geq 2^{6}\)，另一方面，\(X_5\) 稳定 \(v_0,v_1\)，因而是 \(A_{v_0v_1}\) 的子群，据引理 2 的讨论，\(\lvert A_{v_0 v_1} \rvert=2^6\)，故 \(\lvert X_5 \rvert = 2^6\). 再由严格的子群关系 \(X_0 < X_1 \cdots < X_5\) 以及 \(\lvert X_0 \rvert = 2\)，论断成立.
\([x_0,x_i]\in \langle x_1,\cdots,x_{i-1} \rangle\)
首先，据 \(\lvert X_{i} : X_{i-1} \rvert=2\)，即 \(X_{i-1} \lhd X_i\)，必有 \([x_0,x_i] \in X_{i-1}\)，且从陪集的角度，要么 \([x_0,x_i] \in \langle x_1,\cdots,x_{i-1} \rangle\)，要么 \([x_0,x_i] \in \langle x_1,\cdots,x_{i-1} \rangle x_0\). 欲证论断，只需排除后者. 反证法，假设后者成立，即假设 \(x_i x_0 x_i x_0 \in \langle x_1,\cdots,x_{i-1} \rangle x_0\)，那么 \(x_i x_0 x_i \in \langle x_1,\cdots,x_{i-1} \rangle\)，进而 \(x_i x_0 x_i\) 必固定 \(v_{-1}\)，但是 \(x_i\) 固定 \(v_{-1}\)，且 \(x_0\) 不固定 \(v_{-1}\)，矛盾.
注：至此，我们已证明 \([x_0,x_5]\) 必固定 \(v_2\).
\([a^b,c]=[a,c]^{[a,b]}[[a,b],c]\)
只要验证以下两个恒等式：
- \(a^b=a[a,b]\)
- \([ab,c]=[a,c]^b[b,c]\)
\([x_0,x_2]=1\)
反证法. 假设 \(x_0,x_2\) 不交换，则 \(\langle x_0,x_2 \rangle\) 必生成二面体群，且由 \(\lvert X_2 \rvert = 8\)，必有 \(\langle x_0,x_2 \rangle \cong D_8\)，这就是说 \(X_2=\langle x_0,x_2 \rangle\cong D_8\). 注意到 \(Z(D_8)\) 仅有两个元素，且 \(x_1\) 与 \(x_0,x_2\) 均交换，即 \(Z(D_8)=\{1,x_1\}\)，故 \([x_0,x_2]\) 只能是 \(x_1\). 另一方面，利用 \([x_0,x_3] \in \langle x_1,x_2 \rangle\)，可见 \([[x_0,x_3],x_2]=1\)，这样一来：
\[ [x_0,x_2]^{x_3}=[x_0,x_2]^{[x_0,x_3]}[[x_0,x_3],x_2]=[x_0,x_2]^{[x_0,x_3]} \]
这就是说 \(x_1^{x_3}=x_1^{[x_0,x_3]}=x_1\)，即 \([x_1,x_3]=1\)，进而 \([x_0,x_2]=g^{-1}[x_1,x_3]g=1\)，矛盾.
这样，我们证明了 \(X_2 \cong \mathbb{Z}_2^3\)，且不难得到 \([x_i,x_{i+2}]=1\)，因而 \(\langle x_i,x_{i+1},x_{i+2} \rangle \cong \mathbb{Z}_2^3\).
\([x_0,x_3]=1\)
反证法. 假设 \([x_0,x_3]=h\neq 1\)，注意 \(h \in \langle x_1,x_2 \rangle\)，再利用 \([x_0,x_4] \in \langle x_1,x_2,x_3 \rangle\cong \mathbb Z_2^3\)，必有：
\[ h^{x_4}=[x_0,x_3]^{x_4}=h^{[x_0,x_4]}[[x_0,x_4],x_3]=h \]
再由 \([x_1,x_4]=g[x_0,x_3]g^{-1}\neq 1\)，可知 \(h\neq x_1\). 另一方面，假设 \(h=x_1 x_2\)，则因为 \(x_2^{x_4}=x_2\)，必有 \(x_1^{x_4}=x_1\)，矛盾. 因此 \(h=x_2\). 然而，利用 \([x_0,x_5] \in \langle x_1,x_2,x_3,x_4 \rangle\)，以及 \(\langle x_i,x_{i+1},x_{i+2} \rangle \cong \mathbb{Z}_2^3\)，我们有：
\[ x_2^{x_5}=[x_0,x_3]^{x_5}=x_2^{[x_0,x_5]}[[x_0,x_5],x_3]=x_2 \]
即 \([x_2,x_5]=1\)，进而 \([x_0,x_3]=g^{-2}[x_2,x_5]g^2=1\)，矛盾.
这样，我们证明了 \(X_3 \cong \mathbb{Z}_2^4\)，且不难得到 \([x_i,x_{i+3}]=1\)，因而 \(\langle x_i,x_{i+1},x_{i+2},x_{i+3} \rangle \cong \mathbb{Z}_2^4\).
\([x_0,x_4]\neq 1\)
反证法. 假设 \([x_0,x_4]=1\)，那么 \(x_0\) 将固定这样一条 \(8\)-弧：
\[ v_6^{x_4}-v_5^{x_4}-v_4^{x_4}-v_3^{x_4}-v_2-v_3-v_4-v_5-v_6 \].
即 \(x_0=1\)，矛盾.
\([x_0,x_4] \in \langle x_2,x_3 \rangle\)
由上一条，\([x_1,x_5]=g[x_0,x_4]g^{-1}\neq 1\)，另一方面，由 \([x_0,x_4] \in \langle x_1,x_2,x_3 \rangle\) 以及 \([x_0,x_5] \in \langle x_1,x_2,x_3,x_4 \rangle\)，有：
\[ [x_0,x_4]^{x_5}=[x_0,x_4]^{[x_0,x_5]}[[x_0,x_5],x_4]=[x_0,x_4] \]
因而 \([x_0,x_4]\) 与 \(x_5\) 交换，而 \([x_1,x_5]\neq 1\)，故论断成立.
\([x_0,x_5] \in \langle x_1,x_2,x_3 \rangle\)
反证法，假设 \([x_0,x_5]=k x_4, k \in \langle x_1,x_2,x_3 \rangle\)，注意 \(k\) 与 \(x_0,x_4\) 交换且至多二阶，故有
\[ [x_0,x_4]=[x_0,k x_4]=[x_0,[x_0,x_5]]=(x_0 x_0 x_5 x_0 x_5)^2=x_5 x_0 x_5 x_5 x_0 x_5 =1 \]
矛盾.
至此，\([x_0,x_5]\in \langle x_1,x_2,x_3 \rangle\) 必固定 \(v_2,v_3\)，命题得证.