# Symmetric graph

## Graph in which all ordered pairs of linked nodes are automorphic / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Symmetric graph?

Summarize this article for a 10 year old

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

- $f:V(G)\rightarrow V(G)$

such that

- $f(u_{1})=u_{2}$ and $f(v_{1})=v_{2}.$
^{[1]}

In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction).^{[2]} Such a graph is sometimes also called **1-arc-transitive**^{[2]} or **flag-transitive**.^{[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 edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Star graphs are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, semi-symmetric graphs are edge-transitive and regular, but not vertex-transitive.

**Quick Facts**Graph families defined by their automorphisms, → ...

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 |

Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree.^{[3]} However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.^{[4]} Such graphs are called half-transitive.^{[5]} The smallest connected half-transitive 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 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.^{[1]}

A t-arc is defined to be a sequence of *t* + 1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A **t-transitive graph** is a graph such that the automorphism group acts transitively on t-arcs, but not on (t + 1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be t-transitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2-transitive, for example.^{[1]}

Note that conventionally the term "symmetric graph" is not complementary to the term "asymmetric graph," as the latter refers to a graph that has no nontrivial symmetries at all.