In the mathematical field of graph theory, a graph G is symmetric (or arctransitive) if, given any two pairs of linked vertices u_{1}—v_{1} and u_{2}—v_{2} 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 linked vertices (that is, upon edges considered as having a direction).^{[2]} Such a graph is sometimes also called 1arctransitive^{[2]} or flagtransitive.^{[3]}
By definition (ignoring u_{1} and u_{2}), a symmetric graph without isolated vertices must also be vertex transitive.^{[1]} Since the definition above maps one edge to another, a symmetric graph must also be edge transitive. However, an edgetransitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Semisymmetric graphs, for example, are edgetransitive and regular, but not vertextransitive.
Graph families defined by their automorphisms  
distancetransitive  distanceregular  strongly regular  
symmetric (arctransitive)  ttransitive, t ≥ 2  
_{ (if connected)}  
vertex and edgetransitive  edgetransitive and regular  edgetransitive  
vertextransitive  regular  
Cayley graph  skewsymmetric 
Every connected symmetric graph must thus be both vertextransitive and edgetransitive, and the converse is true for graphs of odd degree.^{[3]} However, for even degree, there exist connected graphs which are vertextransitive and edgetransitive, but not symmetric.^{[4]} Such graphs are called halftransitive.^{[5]} The smallest connected halftransitive graph is Holt's graph, with degree 4 and 27 vertices.^{[1]}^{[6]} Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertextransitive and edgetransitive, rather than an arctransitive graph. Such a definition would include halftransitive graphs, which are excluded under the definition above.
A distancetransitive graph is one where instead of considering pairs of linked 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.^{[1]}
A tarc is defined to be a sequence of t+1 linked vertices, with any repeated vertices being more than 2 steps apart. A ttransitive graph is a graph such that the automorphism group acts transitively on tarcs, but not on (t+1)arcs. Since 1arcs are simply edges, every symmetric graph of degree 3 or more must be ttransitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2transitive, for example.^{[1]}
Contents 
Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The Foster census and its extensions provide such lists.^{[7]} The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs,^{[8]} and in 1988 (when Foster was 92^{[1]}) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.^{[9]} The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices^{[10]}^{[11]} (ten of these are also distancetransitive; the exceptions are as indicated):
Vertices  Diameter  Girth  Graph  Notes 

4  1  3  The complete graph K_{4}  distancetransitive, 2transitive 
6  2  4  The complete bipartite graph K_{3,3}  distancetransitive, 3transitive 
8  3  4  The vertices and edges of the cube  distancetransitive, 2transitive 
10  2  5  The Petersen graph  distancetransitive, 3transitive 
14  3  6  The Heawood graph  distancetransitive, 4transitive 
16  4  6  The Möbius–Kantor graph  2transitive 
18  4  6  The Pappus graph  distancetransitive, 3transitive 
20  5  5  The vertices and edges of the dodecahedron  distancetransitive, 2transitive 
20  5  6  The Desargues graph  distancetransitive, 3transitive 
24  4  6  The Nauru graph (the generalized Petersen graph G(12,5))  2transitive 
26  5  6  The F26A graph^{[11]}  1transitive 
28  4  7  The Coxeter graph  distancetransitive, 3transitive 
30  4  8  The Tutte–Coxeter graph  distancetransitive, 5transitive 
Other well known cubic symmetric graphs are the Dyck graph, the Foster graph and the Biggs–Smith graph. The ten distancetransitive graphs listed above, together with the Foster graph and the Biggs–Smith graph, are the only cubic distancetransitive graphs.
Noncubic symmetric graphs include cycle graphs (of degree 2), complete graphs (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron, icosahedron, cuboctahedron, and icosidodecahedron. The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree.
The vertexconnectivity of a symmetric graph is always equal to the degree d.^{[3]} In contrast, for vertextransitive graphs in general, the vertexconnectivity is bounded below by 2(d+1)/3.^{[2]}
A ttransitive graph of degree 3 or more has girth at least 2(t–1). However, there are no finite ttransitive graphs of degree 3 or more for t ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for t ≥ 6.
