图的[公式]自同构是指从[公式]到[公式]的映射，若对于任意顶点[公式]，都存在[公式]的自同构将[公式]映射到[公式]，则图[公式]是顶点传递的。从邻接矩阵来看，[公式]的自同构是[公式]的一些排列，将这些排列应用到[公式]的行和列上，[公式]并不改变。

举例来说，[公式]上存在两个自同构。一个是恒等映射，另一个是1和4对换，2和3对换的排列。

需要注意的是，[公式]和[公式]的对换不是[公式]的自同构。尽管上面路和下面的路(边集合是[公式])是同构的。

在完全二部图[公式]中，排列一个部集的顶点并不改变邻接矩阵，这产生了[公式]个自同构。当[公式]时，我们也可以交换部集；[公式]有[公式]个自同构。

二部图[公式]是顶点传递的当且仅当[公式]。如果[公式]，那么[公式]不是顶点传递的，但每个圈都是顶点传递的。[公式]图是点传递的。

这也表明了一个思想，对于点传递图，证明一个顶点的相关命题，就可以得到整个图关于顶点的命题。顶点传递性保证了每个顶点看起来相同。我们有时说一个顶点和另一个顶点是对称的，我们只需证明其中一个就行。这意味着图中存在两个点存在一个对换，而这个对换是图[公式]的自同构。

例题

参考 West 图论教材