Editing Cayley graph (section)

== Definition ==
Let <math>G</math> be a [[group (mathematics)|group]] and <math>S</math> be a [[generating set of a group|generating set]] of <math>G</math>. The Cayley graph <math>\Gamma = \Gamma(G,S)</math> is an [[Edge coloring|edge-colored]] [[directed graph]] constructed as follows:<ref name=Cayley78>{{cite journal|first1= Arthur |last1=Cayley|journal= American Journal of Mathematics | year=1878|volume=1|issue=2|pages=174–6|title=Desiderata and suggestions: No. 2. The Theory of groups: graphical representation | url=https://babel.hathitrust.org/cgi/pt?id=uc1.$c239465;view=1up;seq=194|jstor=2369306|doi=10.2307/2369306}} In his Collected Mathematical Papers 10: 403–405.</ref>

* Each element <math>g</math> of <math>G</math> is assigned a vertex: the vertex set of <math>\Gamma</math> is identified with <math>G.</math>
* Each element <math>s</math> of <math>S</math> is assigned a color <math>c_s</math>.
* For every <math>g \in G</math> and <math>s \in S</math>, there is a directed edge of color <math>c_s</math> from the vertex corresponding to <math>g</math> to the one corresponding to <math>gs</math>. 

Not every convention requires that <math>S</math> generate the group. If <math>S</math> is not a generating set for <math>G</math>, then <math>\Gamma</math> is [[connectivity (graph theory)|disconnected]] and each connected component represents a coset of the subgroup generated by <math>S</math>.

If an element <math>s</math> of <math>S</math> is its own inverse, <math>s = s^{-1},</math> then it is typically represented by an undirected edge.

The set <math>S</math> is often assumed to be finite, especially in [[geometric group theory]], which corresponds to <math>\Gamma</math> being locally finite and <math>G</math> being finitely generated.

The set <math>S</math> is sometimes assumed to be [[Symmetric set|symmetric]] (<math>S = S^{-1}</math>) and not containing the group [[identity element]]. In this case, the uncolored Cayley graph can be represented as a simple undirected [[graph (discrete mathematics)|graph]].