Vertex-Transitive Graph

A vertex-transitive graph, also called a point-symmetric graph by Harary and Palmer (1973, p. 263) and sometimes a node symmetric graph (Chiang and Chen 1995), is a graph such that every pair of vertices is equivalent under some element of its automorphism group. More explicitly, a vertex-transitive graph is a graph whose automorphism group is transitive (Holton and Sheehan 1993, p. 27). Informally speaking, a graph is vertex-transitive if every graph vertex has the same local environment, so that no graph vertex can be distinguished from any other based on the vertices and edges surrounding it.

Another way of characterizing a vertex-transitive graph is as a graph for which the automorphism group has a single group orbit (i.e., the group orbit lengths of its graph automorphism group are a single number).

A graph may be tested to determine if it is vertex-transitive in the Wolfram Language using VertexTransitiveGraphQ[g].

A graph in which every edge has the same local environment, so that no graph edge can be distinguished from any other, is said to be edge-transitive. A connected undirected graph is edge-transitive if its line graph is vertex-transitive.

All vertex-transitive graphs are regular, but not necessarily vice versa. A regular graph that is edge-transitive but not vertex-transitive is called a semisymmetric graph. MathWorld calls a graph that is both edge-transitive and vertex-transitive a symmetric graph (Holton and Sheehan 1993, pp. 209-210); see that entry for alternative terminology.

The Lovász conjecture asserts that without exception, every connected vertex-transitive graph is traceable.

Ma and Zhao (2026) proved that every finite connected vertex-transitive graph on vertices has graph circumference at least for an absolute constant . For all sufficiently large vertex degrees , the bound improves to .

Furthermore, there are exactly five known connected nonhamiltonian vertex-transitive graphs, namely the path graph , the Petersen graph , the Coxeter graph , the triangle-replaced Petersen, and the triangle-replaced Coxeter graph. As attributed by Gould (1991) citing Bermond (1979), Thomassen conjectured that all other connected vertex-transitive graphs are Hamiltonian (cf. Godsil and Royle 2001, p. 45; Mütze 2024).

The numbers of simple graphs with , 2, ... nodes that are vertex-transitive are 1, 2, 2, 4, 3, 8, 4, 14, 9, ... (OEIS A006799; McKay 1990; Colbourn and Dinitz 1996).

The numbers of simple -node connected graphs that are vertex-transitive for , 2, ... are 1, 1, 1, 2, 2, 5, 3, 10, 7, ... (OEIS A006800; McKay and Royle 1990).