Symmetric graph

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	t-transitive, t ≥ 2		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u₁—v₁ and u₂—v₂ of G, there is an automorphism

such that

In other words, a graph is symmetric if its automorphism group acts transitively upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive.

By definition (ignoring u₁ and u₂), a symmetric graph without isolated vertices must also be vertex transitive. Since the definition above maps one edge to another, a symmetric graph must also be edge transitive. However, an edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Semi-symmetric graphs, for example, are edge-transitive and regular, but not vertex-transitive.

Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree. However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric. Such graphs are called half-transitive. The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices. Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.

A distance-transitive graph is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.

...
Wikipedia