对换图Γ的性质证明：n≥5时n-1点完全子图的形式
先把问题再明确一下：
我们定义图$\Gamma$：
- 顶点集合是对称群$S_n$中的所有对换（也就是形如$(i,j)$的2-循环，$i\neq j$）；
- 两个顶点之间有边，当且仅当对应的两个对换有一个公共的移动点（也就是它们的循环表示里有共同的元素）。
需要证明的是：当$n\geq5$时，$\Gamma$中任意一个$n-1$个顶点的完全子图，都一定是形如$G_a := {(a,x) \mid x \in {1,2,...,n} \setminus {a}}$的集合——换句话说，这个完全子图里的所有对换，都共享同一个公共移动点$a$。
证明过程
咱们用反证法来推导：假设存在一个$n-1$个顶点的完全子图$H$，它不是任何一个$G_a$的形式，也就是说，不存在一个公共点$a$，使得$H$里的所有对换都包含$a$。接下来我们会导出矛盾。
步骤1：分析$H$中对换的相交性质
因为$H$是完全子图，所以$H$里的任意两个对换都必须有公共移动点（不然它们之间就没有边，不符合完全子图的定义）。但我们假设$H$没有全局公共点，也就是说：
对于每个点$x \in {1,2,...,n}$，都存在$H$中的某个对换，它不含$x$。
步骤2：构造初始的三个对换
先从$H$里任取一个对换$t=(a,b)$。根据上面的假设，存在$H$中的对换$s$不含$a$——但$s$必须和$t$有公共点，所以$s$只能包含$b$，不妨设$s=(b,c)$。
再根据假设，存在$H$中的对换$u$不含$b$——$u$必须和$t$有公共点（所以含$a$），同时必须和$s$有公共点（所以含$c$），因此$u=(a,c)$。
现在$H$里已经有了三个对换：$(a,b)$、$(b,c)$、$(a,c)$。
步骤3：导出矛盾（利用$n\geq5$的条件）
因为$n\geq5$，所以$n-1\geq4$，也就是说$H$里至少还有一个额外的对换$v$，不属于上面三个。
现在看$v$的可能：
- $v$必须和$t=(a,b)$相交，所以$v$要么含$a$，要么含$b$；
- $v$必须和$s=(b,c)$相交，所以$v$要么含$b$，要么含$c$；
- $v$必须和$u=(a,c)$相交，所以$v$要么含$a$，要么含$c$。
把这些条件组合起来，$v$的可能形式只能是：
- $(a,b)$、$(b,c)$、$(a,c)$：但这三个已经在$H$里了，$v$是新的对换，排除；
- $(a,d)$（$d\neq a,b,c$）：这个对换和$s=(b,c)$没有公共点，违反了完全子图的要求（它们之间应该有边，但实际没有）；
- $(b,d)$（$d\neq a,b,c$）：这个对换和$u=(a,c)$没有公共点，同样违反要求；
- $(c,d)$（$d\neq a,b,c$）：这个对换和$t=(a,b)$没有公共点，还是违反要求。
也就是说，根本不存在这样的额外对换$v$，但这和$H$有$n-1\geq4$个顶点矛盾！
步骤4：结论
我们的假设（$H$不是$G_a$的形式）不成立，因此所有$n-1$个顶点的完全子图都必须是$G_a$的形式——也就是所有对换共享同一个公共移动点$a$。
内容的提问来源于stack exchange，提问作者Atvin
