Asymmetric 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

The 8 6-vertex asymmetric graphs

The Frucht graph, the smallest asymmetric cubic graph.

In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries.

Formally, an automorphism of a graph is a permutation p of its vertices with the property that any two vertices u and v are adjacent if and only if p(u) and p(v) are adjacent. The identity mapping of a graph onto itself is always an automorphism, and is called the trivial automorphism of the graph. An asymmetric graph is a graph for which there are no other automorphisms.

The smallest asymmetric non-trivial graphs have 6 vertices. The smallest asymmetric tree has seven vertices: it consists of three paths of lengths 1, 2, and 3, linked at a common endpoint. The smallest asymmetric cubic graph is the Frucht graph discovered in 1939. According to a strengthened version of Frucht's theorem, there are infinitely many asymmetric cubic graphs.

The proportion of graphs on n vertices with nontrivial automorphism tends to zero as n grows, which is informally expressed as "almost all finite graphs are asymmetric". In contrast, again informally, "almost all infinite graphs are symmetric". More specifically, countable infinite random graphs in the Erdős–Rényi model are, with probability 1, isomorphic to the highly symmetric Rado graph.