Cayley graph

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group[1] is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley) and uses a specified, usually finite, set of generators for the group. It is a central tool in combinatorial and geometric group theory.

The Cayley graph of the free group on two generators a and b
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)
Cayley graph zero-symmetric asymmetric


Suppose that   is a group and   is a generating set of  . The Cayley graph   is a colored directed graph constructed as follows:[2]

  • Each element   of   is assigned a vertex: the vertex set   of   is identified with  
  • Each generator   of   is assigned a color  .
  • For any   and   the vertices corresponding to the elements   and   are joined by a directed edge of colour   Thus the edge set   consists of pairs of the form   with   providing the color.

In geometric group theory, the set   is usually assumed to be finite, symmetric (i.e.  ) and not containing the identity element of the group. In this case, the uncolored Cayley graph is an ordinary graph: its edges are not oriented and it does not contain loops (single-element cycles).


  • Suppose that   is the infinite cyclic group and the set   consists of the standard generator 1 and its inverse (−1 in the additive notation) then the Cayley graph is an infinite path.
  • Similarly, if   is the finite cyclic group of order   and the set   consists of two elements, the standard generator of   and its inverse, then the Cayley graph is the cycle  . More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs.
  • The Cayley graph of the direct product of groups (with the cartesian product of generating sets as a generating set) is the cartesian product of the corresponding Cayley graphs.[3] Thus the Cayley graph of the abelian group   with the set of generators consisting of four elements   is the infinite grid on the plane  , while for the direct product   with similar generators the Cayley graph is the   finite grid on a torus.
Cayley graph of the dihedral group   on two generators a and b
Cayley graph of  , on two generators which are both self-inverse
  • A Cayley graph of the dihedral group   on two generators   and   is depicted to the left. Red arrows represent composition with  . Since   is self-inverse, the blue lines, which represent composition with  , are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The Cayley table of the group   can be derived from the group presentation
A different Cayley graph of   is shown on the right.   is still the horizontal reflection and is represented by blue lines, and   is a diagonal reflection and is represented by pink lines. As both reflections are self-inverse the Cayley graph on the right is completely undirected. This graph corresponds to the presentation
  • The Cayley graph of the free group on two generators   and   corresponding to the set   is depicted at the top of the article, and   represents the identity element. Travelling along an edge to the right represents right multiplication by   while travelling along an edge upward corresponds to the multiplication by   Since the free group has no relations, the Cayley graph has no cycles. This Cayley graph is a 4-regular infinite tree and is a key ingredient in the proof of the Banach–Tarski paradox.
Part of a Cayley graph of the Heisenberg group. (The coloring is only for visual aid.)
is depicted to the right. The generators used in the picture are the three matrices   given by the three permutations of 1, 0, 0 for the entries  . They satisfy the relations  , which can also be understood from the picture. This is a non-commutative infinite group, and despite being a three-dimensional space, the Cayley graph has four-dimensional volume growth.[citation needed]
Cayley Q8 graph showing cycles of multiplication by quaternions i, j and k


The group   acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of   on its Cayley graph. Explicitly, an element   maps a vertex   to the vertex   The set of edges within the Cayley graph is preserved by this action: the edge   is transformed into the edge  . The left multiplication action of any group on itself is simply transitive, in particular, the Cayley graph is vertex transitive. This leads to the following characterization of Cayley graphs:

Sabidussi's Theorem. A graph   is a Cayley graph of a group   if and only if it admits a simply transitive action of   by graph automorphisms (i.e. preserving the set of edges).[4]

To recover the group   and the generating set   from the Cayley graph   select a vertex   and label it by the identity element of the group. Then label each vertex   of   by the unique element of   that transforms   into   The set   of generators of   that yields   as the Cayley graph is the set of labels of the vertices adjacent to the selected vertex. The generating set is finite (this is a common assumption for Cayley graphs) if and only if the graph is locally finite (i.e. each vertex is adjacent to finitely many edges).

Elementary propertiesEdit

  • If a member   of the generating set is its own inverse,   then it is typically represented by an undirected edge.
  • The Cayley graph   depends in an essential way on the choice of the set   of generators. For example, if the generating set   has   elements then each vertex of the Cayley graph has   incoming and   outgoing directed edges. In the case of a symmetric generating set   with   elements, the Cayley graph is a regular directed graph of degree  
  • Cycles (or closed walks) in the Cayley graph indicate relations between the elements of   In the more elaborate construction of the Cayley complex of a group, closed paths corresponding to relations are "filled in" by polygons. This means that the problem of constructing the Cayley graph of a given presentation   is equivalent to solving the Word Problem for  .[1]
  • If   is a surjective group homomorphism and the images of the elements of the generating set   for   are distinct, then it induces a covering of graphs
where   In particular, if a group   has   generators, all of order different from 2, and the set   consists of these generators together with their inverses, then the Cayley graph   is covered by the infinite regular tree of degree   corresponding to the free group on the same set of generators.
  • A graph   can be constructed even if the set   does not generate the group   However, it is disconnected and is not considered to be a Cayley graph. In this case, each connected component of the graph represents a coset of the subgroup generated by  
  • For any finite Cayley graph, considered as undirected, the vertex connectivity is at least equal to 2/3 of the degree of the graph. If the generating set is minimal (removal of any element and, if present, its inverse from the generating set leaves a set which is not generating), the vertex connectivity is equal to the degree. The edge connectivity is in all cases equal to the degree.[5]
  • Every group character   of the group   induces an eigenvector of the adjacency matrix of  . When   is Abelian, the associated eigenvalue is
In particular, the associated eigenvalue of the trivial character (the one sending every element to 1) is the degree of  , that is, the order of  . If   is an Abelian group, there are exactly   characters, determining all eigenvalues.

Schreier coset graphEdit

If one, instead, takes the vertices to be right cosets of a fixed subgroup   one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd–Coxeter process.

Connection to group theoryEdit

Knowledge about the structure of the group can be obtained by studying the adjacency matrix of the graph and in particular applying the theorems of spectral graph theory.

The genus of a group is the minimum genus for any Cayley graph of that group.[6]

Geometric group theoryEdit

For infinite groups, the coarse geometry of the Cayley graph is fundamental to geometric group theory. For a finitely generated group, this is independent of choice of finite set of generators, hence an intrinsic property of the group. This is only interesting for infinite groups: every finite group is coarsely equivalent to a point (or the trivial group), since one can choose as finite set of generators the entire group.

Formally, for a given choice of generators, one has the word metric (the natural distance on the Cayley graph), which determines a metric space. The coarse equivalence class of this space is an invariant of the group.


Cayley graphs were first considered for finite groups by Arthur Cayley in 1878.[2] Max Dehn in his unpublished lectures on group theory from 1909–10 reintroduced Cayley graphs under the name Gruppenbild (group diagram), which led to the geometric group theory of today. His most important application was the solution of the word problem for the fundamental group of surfaces with genus ≥ 2, which is equivalent to the topological problem of deciding which closed curves on the surface contract to a point.[7]

Bethe latticeEdit

The Bethe lattice or infinite Cayley tree is the Cayley graph of the free group on   generators. A presentation of a group   by   generators corresponds to a surjective map from the free group on   generators to the group   and at the level of Cayley graphs to a map from the infinite Cayley tree to the Cayley graph. This can also be interpreted (in algebraic topology) as the universal cover of the Cayley graph, which is not in general simply connected.

See alsoEdit


  1. ^ a b Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Courier. ISBN 978-0-486-43830-6.
  2. ^ a b Cayley, Arthur (1878). "Desiderata and suggestions: No. 2. The Theory of groups: graphical representation". American Journal of Mathematics. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical Papers 10: 403–405.
  3. ^ Theron, Daniel Peter (1988), An extension of the concept of graphically regular representations, Ph.D. thesis, University of Wisconsin, Madison, p. 46, MR 2636729.
  4. ^ Sabidussi, Gert (October 1958). "On a class of fixed-point-free graphs". Proceedings of the American Mathematical Society. 9 (5): 800–4. doi:10.1090/s0002-9939-1958-0097068-7. JSTOR 2033090.
  5. ^ See Theorem 3.7 of Babai, László (1995). "Chapter 27: Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.). Handbook of Combinatorics. Amsterdam: Elsevier. pp. 1447–1540.
  6. ^ White, Arthur T. (1972). "On the genus of a group". Transactions of the American Mathematical Society. 173: 203–214. doi:10.1090/S0002-9947-1972-0317980-2. MR 0317980.
  7. ^ Dehn, Max (2012) [1987]. Papers on Group Theory and Topology. Springer-Verlag. ISBN 1461291070. Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.

External linksEdit