Editing Cayley graph (section)

== Elementary properties ==

* The Cayley graph <math>\Gamma(G,S)</math> depends in an essential way on the choice of the set <math>S</math> of generators. For example, if the generating set <math>S</math> has <math>k</math> elements then each vertex of the Cayley graph has <math>k</math> incoming and <math>k</math> outgoing directed edges. In the case of a symmetric generating set <math>S</math> with <math>r</math> elements, the Cayley graph is a [[regular graph|regular directed graph]] of degree <math>r.</math>
* [[Cycle (graph theory)|Cycles]] (or ''closed walks'') in the Cayley graph indicate [[Presentation of a group|relations]] among the elements of <math>S.</math> In the more elaborate construction of the [[Cayley complex]] of a group, closed paths corresponding to relations are "filled in" by [[polygon]]s. This means that the problem of constructing the Cayley graph of a given presentation <math>\mathcal{P}</math> is equivalent to solving the [[Word problem for groups|Word Problem]] for <math>\mathcal{P}</math>.<ref name = CGT/>
* If <math>f: G'\to G</math> is a [[surjective]] [[group homomorphism]] and the images of the elements of the generating set <math>S'</math> for <math>G'</math> are distinct, then it induces a covering of graphs <math display="block"> \bar{f}: \Gamma(G',S')\to \Gamma(G,S),</math> where <math>S = f(S').</math> In particular, if a group <math>G</math> has <math>k</math> generators, all of order different from 2, and the set <math>S</math> consists of these generators together with their inverses, then the Cayley graph <math>\Gamma(G,S)</math> is covered by the infinite regular [[tree (graph theory)|tree]] of degree <math>2k</math> corresponding to the [[free group]] on the same set of generators.
* For any finite Cayley graph, considered as undirected, the [[Connectivity (graph theory)|vertex connectivity]] is at least equal to 2/3 of the [[Degree (graph theory)|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 [[Connectivity (graph theory)|edge connectivity]] is in all cases equal to the degree.<ref>See Theorem 3.7 of {{cite book | chapter=27. Automorphism groups, isomorphism, reconstruction|title=Handbook of Combinatorics|pages=1447–1540|editor1-first=Ronald L.|editor1-last=Graham|editor1-link= Ronald Graham|editor2-first=Martin|editor2-last=Grötschel|editor2-link= Martin Grötschel |editor3-first=László|editor3-last=Lovász|editor3-link=László Lovász|first=László|last=Babai|author-link=László Babai| publisher=Elsevier|volume=1 |isbn=9780444823465 |url=https://books.google.com/books?id=5Y9NCwlx63IC |year=1995|chapter-url=http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf}}</ref>
* If <math>\rho_{\text{reg}}(g)(x) = gx</math> is the left-regular representation with <math>|G|\times |G|</math> matrix form denoted <math>[\rho_{\text{reg}}(g)]</math>, the adjacency matrix of <math>\Gamma(G,S)</math> is <math display="inline">A = \sum_{s\in S} [\rho_{\text{reg}}(s)]</math>.
* Every group [[Multiplicative character|character]] <math>\chi</math> of the group <math>G</math> induces an [[eigenvector]] of the [[adjacency matrix]] of <math>\Gamma(G,S)</math>. The associated [[eigenvalue]] is  <math display="block">\lambda_\chi=\sum_{s\in S}\chi(s),</math> which, when <math>G</math> is Abelian, takes the form <math display="block">\sum_{s\in S} e^{2\pi ijs/|G|}</math> for integers <math>j = 0,1,\dots,|G|-1.</math> In particular, the associated eigenvalue of the trivial character (the one sending every element to 1) is the degree of <math>\Gamma(G,S)</math>, that is, the order of <math>S</math>. If <math>G</math> is an [[Abelian group]], there are exactly <math>|G|</math> characters, determining all eigenvalues. The corresponding orthonormal basis of eigenvectors is given by <math>v_j = \tfrac{1}{\sqrt{|G|}}\begin{pmatrix} 1 & e^{2\pi ij/|G|} & e^{2\cdot 2\pi ij/|G|} & e^{3\cdot 2\pi ij/|G|} & \cdots & e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}.</math> It is interesting to note that this eigenbasis is independent of the generating set <math>S</math>. {{pb}} More generally for symmetric generating sets, take <math>\rho_1,\dots,\rho_k</math> a complete set of irreducible representations of <math>G,</math> and let <math display="inline">\rho_i(S) = \sum_{s\in S} \rho_i(s)</math> with eigenvalue set <math>\Lambda_i(S)</math>. Then the set of eigenvalues of <math>\Gamma(G,S)</math> is exactly <math display="inline">\bigcup_i \Lambda_i(S),</math> where eigenvalue <math>\lambda</math> appears with multiplicity <math>\dim(\rho_i)</math> for each occurrence of <math>\lambda</math> as an eigenvalue of <math>\rho_i(S).</math>