图自同构

图自同构是一个图到自身的同构：它重新排列顶点，同时保持所有顶点对的相邻和不相邻关系。图的自同构刻画抽象连接结构的对称性，与某次画图的外形是否对称有关联，但并不依赖这次画图的具体位置。

四顶点环的对称性

设图为四顶点环 $C_4$，顶点按顺时针标为 $1,2,3,4$。轮换 $$1\mapsto 2,2\mapsto 3,3\mapsto 4,4\mapsto 1$$ 把每条环边映成另一条环边，所以是自同构。反射 $1\mapsto 1,2\mapsto 4,3\mapsto 3,4\mapsto 2$ 也是自同构。恒等映射始终是自同构。

环的四个位置均可成为顶点一的像；确定顶点二的像后，其他像也确定。

精确计数

自同构必须把顶点 1 映到四个顶点之一。顶点 2 与 1 相邻，所以其像只能是所选像的两个邻居之一。一旦这两个像确定，顶点 4 必须映到另一邻居，顶点 3 再映到唯一剩余的顶点。因此最多有 $4\times 2=8$ 个自同构。

这八种选择都成立：四个轮换与四个反射均保持环边及非边。因此 $|\mathrm{Aut}(C_4)|=8$。同理，对 $n\ge 3$ 的环 $C_n$，顶点 1 有 $n$ 个像、顶点 2 有两个选择，故共有 $2n$ 个自同构。

自同构群

两个自同构先后作用，所得映射仍保持顶点间相邻关系；每个自同构的逆映射也保持相邻关系。连同恒等映射，所有自同构在映射复合下构成群 $\mathrm{Aut}(G)$。例如上面的顺时针轮换连续应用四次就是恒等映射。

对于完全图 $K_n$，任意顶点置换都把边映为边，也把不同顶点映成不同顶点，因此自同构群包含所有 $n!$ 个置换。相反，某些图只有恒等自同构。判断时应检查连接结构；图形看起来不对称，不能单独证明它没有非平凡的自同构。