graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a branch of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

is called an asymmetric graph if it has no nontrivial

symmetries Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...

. Formally, an

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

of a graph is a

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

of its vertices with the property that any two vertices and are adjacent

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

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 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 map (mathematics), mapping the object to itself while preserving all of its structure. The Set (m ...

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 In the mathematical field of graph theory, a graph is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices (u_1,v_1) and (u_2,v_2) of , there is an automorphism :f : V(G) \rightarrow V(G) such that :f(u_1) = u_2 a ...

," as the latter refers to a stronger condition than possessing nontrivial symmetries.

Examples

The smallest asymmetric

non-trivial In mathematics, the adjective trivial is often used to refer to a claim or a case which can be readily obtained from context, or a particularly simple object possessing a given structure (e.g., group, topological space). The noun triviality usual ...

graphs have 6 vertices. The smallest asymmetric

regular graph In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...

s have ten vertices; there exist asymmetric graphs that are and . 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 bip ...

s is the twelve-vertex

Frucht graph In the mathematics, mathematical field of graph theory, the Frucht graph is a cubic graph with 12 Vertex (graph theory), vertices, 18 edges, and no nontrivial graph automorphism, symmetries. It was first described by Robert Frucht in 1949. The F ...

discovered in 1939.. According to a strengthened version of

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

, 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 a nontrivial automorphism tends to zero as ''n'' grows, which is informally expressed as "

almost all In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...

finite graphs are asymmetric". In contrast, again informally, "almost all infinite graphs have nontrivial symmetries." More specifically,

countably 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 l ...

s in the

Erdős–Rényi model In the mathematical field of graph theory, the Erdős–Rényi model refers to one of two closely related models for generating random graphs or the evolution of a random network. These models are named after Hungarians, Hungarian mathematicians ...

are, with probability 1,

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

to the highly symmetric

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

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, e.g., including only woody plants with secondary growth, only ...

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 Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...

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