Grafo de Cayley del grupo libre de dos generadores, a y b.
Sea un grupo y un subconjunto.
El grafo de Cayley cumple:
los vértices del grafo son los elementos del grupo :
el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que gs=h:o equivalentemente, si g-1h pertenece a S:
El segundo punto es en ocasiones cambiado por lo siguiente: el par ordenado (g,h) es una arista del grafo si existe s perteneciente a S tal que sg=h (o, de forma equivalente, si hg-1 pertenece a S).
En general se estudia el grafo de Cayley con Sgenerador del grupo G (lo que hace al grafo conexo) y tal que el neutro del grupo no está en S (de esta manera no hay lazos en el grafo). Además, suele asumirse que el conjunto S es simétrico, es decir, si t pertenece a S entonces t-1 también. Esta última propiedad hace al grafo de Cayley no orientado.
Grafo de Cayley de S3 con conjunto de generadores {(12), (23), (13)}Grafo de Cayley del grupo S3 con conjunto de generadores {(12), (123)}
Si el grupo es con la operación suma y tomamos como conjunto generador a S={1} entonces el grafo de Cayley resulta un camino infinito, con aristas uniendo cada entero con su consecutivo.
El grafo del grupo con S={1,-1} es el grafo cicloCn.
Si G es un grupo cualquiera con n elementos y tomamos S=G-{e} entonces su grafo de Cayley será el grafo completoKn.
El grafo de Cayley no es independiente del conjunto de generadores que se toma. Es decir, que tomando dos generadores distintos obtenemos en general grafos no isomorfos. Vea por ejemplo las imágenes a la derecha donde se muestran dos grafos de Cayley distintos, ambos correspondientes al grupo simétricoS3.
Si S tiene k elementos y es simétrico (y por lo tanto el grafo es no dirigido) entonces el grafo es k-regular. Además, es transitivo en los vértices, o sea, dados dos vértices cualesquiera existe un automorfismo del grafo que lleva un vértice en el otro.[2] Sin embargo, no todo grafo transitivo en vértices es el grafo de Cayley de algún grupo.[3]
Un ciclo en el grafo de Cayley indica una relación no trivial en el grupo. De ahí que los únicos grafos de Cayley sin ciclos sean los de los grupos libres, siempre que el grupo no posea elementos de orden 2.[1]
Si S no genera al grupo G entonces habrá varias componentes conexas del grafo, una por cada clase lateral determinada por el subgrupo generado por S.