The following self-contained post relates to definition 1.17, p. 11, of the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier.
Let be a complete graph and its symmetry group. It will be shown that is vertex transitive, i.e. that for any two vertices and there exists a symmetry such that .
The proof is constructive. Given any two vertices and , it suffices to provide a symmetry such that . Although the suggested symmetry is different for every and , the simpler notation is preferred in place of .
Given and , a suitable symmetry can be constructed by swapping with , by redirecting all edges with one end in to edges with one end in and vice versa, and by leaving all other vertices and edges intact.
To formalize the construction, given and , the symmetry is set to satisfy the following seven properties:
- for all vertices other than ,
- , where denotes the edge connecting with ,
- for all other than , where denotes the edge connecting with and the edge connecting with ,
- for all other than , and
- for all other than , where denotes the edge connecting with .
Note that all edges exist in the above construction since is complete, so the symmetry is well-defined.
It is easy to check that the proposed symmetry maps vertices to vertices, edges to edges, and preserves the connectivity of according to the definition of symmetry provided in this blog post. For instance, , , and yield , which is an edge in .