graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

is called an asymmetric graph if it has no nontrivial

symmetries Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...

. 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 Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...

of a graph onto itself is always an automorphism, and is called the

trivial automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphi ...

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 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 outdegr ...

s have ten vertices; there exist ten-vertex asymmetric graphs that are 4-regular and 5-regular. One of the five smallest asymmetric

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bi ...

s is the twelve-vertex

Frucht graph In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939. The Frucht graph is a pancyclic, Halin graph with chromati ...

discovered in 1939.. According to a strengthened version of

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. More strongly, for any fi ...

, 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 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 finite graphs are asymmetric". In contrast, again informally, "almost all infinite graphs are symmetric." More specifically,

countable In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...

infinite

random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs ...

s in the

Erdős–Rényi model In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs or the evolution of a random network. They are named after Hungarian mathematicians Paul Erdős and Alfr� ...

are, with probability 1, isomorphic to the highly symmetric

Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...

Trees

The smallest asymmetric

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

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.

References

{{Commons category, Asymmetric graphs Graph families

Graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...