Editing Cayley graph (section)

== Examples ==
* Suppose that <math>G=\Z</math> is the infinite cyclic group and the set <math>S</math> consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.
* Similarly, if <math>G=\Z_n</math> is the finite [[cyclic group]] of order <math>n</math> and the set <math>S</math> consists of two elements, the standard generator of <math>G</math> and its inverse, then the Cayley graph is the [[cycle graph|cycle]] <math>C_n</math>. More generally, the Cayley graphs of finite cyclic groups are exactly the [[circulant graph]]s.
* 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 graphs|cartesian product]] of the corresponding Cayley graphs.<ref>{{cite thesis | last = Theron | first = Daniel Peter | mr = 2636729 | page = 46 | publisher = University of Wisconsin, Madison | type = Ph.D. thesis | title = An extension of the concept of graphically regular representations | year = 1988}}.</ref>  Thus the Cayley graph of the abelian group <math>\Z^2</math> with the set of generators consisting of four elements <math>(\pm 1,0),(0,\pm 1)</math> is the infinite [[grid graph|grid]] on the plane <math>\R^2</math>, while for the direct product <math>\Z_n \times \Z_m</math> with similar generators the Cayley graph is the <math>n \times m</math> finite grid on a [[torus]].

[[Image:Dih 4 Cayley Graph; generators a, b.svg|220px|left|thumb|Cayley graph of the dihedral group <math>D_4</math> on two generators ''a'' and ''b'']]
[[File:Dih 4 Cayley Graph; generators b, c.svg|170px|right|thumb|Cayley graph of <math>D_4</math>, on two generators which are both self-inverse]]
* A Cayley graph of the [[dihedral group]] <math>D_4</math> on two generators <math>a</math> and <math>b</math> is depicted to the left. Red arrows represent composition with <math>a</math>. Since <math>b</math> is [[Cayley table|self-inverse]], the blue lines, which represent composition with <math>b</math>, are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The [[Cayley table]] of the group <math>D_4</math> can be derived from the [[presentation of a group|group presentation]] <math display="block"> \langle a, b \mid a^4 = b^2 = e, a b = b a^3 \rangle. </math> A different Cayley graph of <math>D_4</math> is shown on the right. <math>b</math> is still the horizontal reflection and is represented by blue lines, and <math>c</math> 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 <math display="block"> \langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle. </math>
* The Cayley graph of the [[free group]] on two generators <math>a</math> and <math>b</math> corresponding to the set <math>S = \{a, b, a^{-1}, b^{-1}\}</math> is depicted at the top of the article, with <math>e</math> being the identity. Travelling along an edge to the right represents right multiplication by <math>a,</math> while travelling along an edge upward corresponds to the multiplication by <math>b.</math>  Since the free group has no [[Presentation of a group|relations]], the Cayley graph has no [[Cycle (graph theory)|cycles]]: it is the 4-[[regular graph|regular]] infinite [[Tree (graph theory)|tree]]. It is a key ingredient in the proof of the [[Banach–Tarski paradox]].
* More generally, the [[Bethe lattice]] or Cayley tree is the Cayley graph of the free group on <math>n</math> generators. A [[Presentation of a group|presentation]] of a group <math>G</math> by <math>n</math> generators corresponds to a surjective [[Group homomorphism|homomorphism]] from the free group on <math>n</math> generators to the group <math>G,</math> defining a map from the Cayley tree to the Cayley graph of <math>G</math>. Interpreting graphs [[Topology|topologically]] as one-dimensional [[Simplicial complex|simplicial complexes]], the [[simply connected]] infinite tree is the [[universal cover]] of the Cayley graph; and the [[Kernel (algebra)#group homomorphism|kernel]] of the mapping is the [[fundamental group]] of the Cayley graph.
[[Image:HeisenbergCayleyGraph.png|thumb|240px|right|Part of a Cayley graph of the Heisenberg group. (The coloring is only for visual aid.)]]
* A Cayley graph of the [[discrete Heisenberg group]]  <math display="block">\left\{ \begin{pmatrix}
 1 & x & z\\
 0 & 1 & y\\
 0 & 0 & 1\\
\end{pmatrix},\ x,y,z \in \Z\right\} </math> is depicted to the right. The generators used in the picture are the three matrices <math>X, Y, Z</math> given by the three permutations of 1, 0, 0 for the entries <math>x, y, z</math>. They satisfy the relations <math>Z = XYX^{-1}Y^{-1}, XZ = ZX, YZ = ZY</math>, which can also be understood from the picture. This is a [[nonabelian group|non-commutative]] infinite group, and despite being embedded in a three-dimensional space, the Cayley graph has four-dimensional [[Growth rate (group theory)|volume growth]].<ref>{{cite conference
 | last = Bartholdi | first = Laurent
 | editor1-last = Ceccherini-Silberstein | editor1-first = Tullio
 | editor2-last = Salvatori | editor2-first = Maura
 | editor3-last = Sava-Huss | editor3-first = Ecaterina
 | arxiv = 1512.07044
 | contribution = Growth of groups and wreath products
 | isbn = 978-1-316-60440-3
 | mr = 3644003
 | pages = 1–76
 | publisher = Cambridge Univ. Press, Cambridge
 | series = London Math. Soc. Lecture Note Ser.
 | title = Groups, graphs and random walks: Selected papers from the workshop held in Cortona, June 2–6, 2014
 | volume = 436
 | year = 2017}}</ref>
[[File:Cayley_Q8_multiplication_graph.svg|thumb|link={{filepath:Cayley_Q8_multiplication_graph.svg}}|Cayley Q8 graph showing cycles of multiplication by [[quaternion]]s {{red|'''i'''}}, {{green|'''j'''}} and {{blue|'''k'''}}]]