Asymmetric 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 of its vertices with the property that any two vertices and are adjacent if and only if and 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. Note that the term "asymmetric graph" is not a negation of the term "symmetric graph," as the latter refers to a stronger condition than possessing nontrivial symmetries. Examples The smallest asymmetric non-trivial graphs have 6 vertices. The smallest asymmetric regular graphs have ten vertices; there exist ten-vertex asymmetric graphs that are 4-regular and 5-regular. One of the five smallest asymmetric cubic graphs is the twelve-vertex Frucht graph discovered in 1939. According to a strengthened version of Frucht's theorem, there are infinitely many asymmetric cubic graphs. Properties The class of asymmetric graphs is closed under complements: a graph G is asymmetric if and only if its complement is. Any n-vertex asymmetric graph can be made symmetric by