Main Page | See live article | Alphabetical index The Cayley graph is a construction that creates a graph out of a group. Given a group G and a subset S such that the identity is in S and such that S-1 = S, the Cayley graph associated with the pair (G,S) is a directed graph which has as vertices the elements of G and for which (g1, g2) is an edge if g1g2-1 is in S. They graph may depend on the choice of the subset S. Cayley Graphs are always vertex-transitive. The Cayley graph is connected if and only if the set S generates the group G. When instead of a subset S we take a subgroup H of finite index in G we obtain a graph that is at the basis of coset enumeration or Todd-Coxeter process. This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.