In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

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

Formally, an automorphism

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....

 of a graph is a permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 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.

Examples

The smallest asymmetric non-trivial graphs have 6 vertices. The smallest asymmetric regular graph

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

s have ten vertices; there exist ten-vertex asymmetric graphs that are 4-regular and 5-regular. One of the two smallest asymmetric cubic graphs is the twelve-vertex Frucht graph

Frucht graph

In the mathematical field of graph theory, the Frucht graph is a 3-regular graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939....

 discovered in 1939. According to a strengthened version of Frucht's theorem

Frucht's theorem

Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph...

, there are infinitely many asymmetric cubic graphs.

Properties

The class of asymmetric graphs is closed under complements

Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

: a graph G is asymmetric if and only if its complement is. Any n-vertex asymmetric graph can be made symmetric by adding and removing a total of at most n/2 + o(n) edges.

Random graphs

The proportion of graphs on n vertices with nontrivial automorphism tends to zero as n grows, which is informally expressed as "almost all

Almost all

In mathematics, the phrase "almost all" has a number of specialised uses."Almost all" is sometimes used synonymously with "all but finitely many" or "all but a countable set" ; see almost....

 finite graphs are asymmetric". In contrast, again informally, "almost all infinite graphs are symmetric." More specifically, countable infinite random graph

Random graph

In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...

s in the Erdős–Rényi model

Erdos–Rényi model

In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...

 are, with probability 1, isomorphic to the highly symmetric Rado graph

Rado graph

In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an...

.

Trees

The smallest asymmetric tree

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

has seven vertices: it consists of three paths of lengths 1, 2, and 3, linked at a common endpoint. In contrast to the situation for graphs, almost all trees are symmetric. In particular, if a tree is chosen uniformly at random among all trees on n labeled nodes, then with probability tending to 1 as n increases, the tree will contain some two leaves adjacent to the same node and will have symmetries exchanging these two leaves.