From Group Operations to Edges
A graph records which pairs of vertices are adjacent. A group supplies a systematic way to make that decision: take the elements of the group as vertices, choose some group elements as allowed steps, and join each vertex to the result of multiplying by one of those steps. This construction turns algebraic data into a graph. To interpret the result correctly, the multiplication convention and the conditions on the chosen steps must be explicit.
Throughout, groups are finite. Write \(e\) for the identity element of a group \(G\), and \(s^{-1}\) for the inverse of \(s\in G\). A subset \(S\subseteq G\) generates \(G\) if every element of \(G\) is a product of elements of \(S\) and their inverses; equivalently, the smallest subgroup containing \(S\) is \(G\). The empty set generates only the trivial group \(\{e\}\).
“Right” specifies that the step \(s\) is multiplied on the right of the current vertex. In a noncommutative group, \(gs\) need not equal \(sg\), so changing the convention can change which elements are adjacent. The definition of edges also makes the conditions for an ordinary simple undirected graph important: there must be no loops, and every adjacency must work in both directions.
When the Construction Is Simple and Undirected
Proof. First suppose \(e\notin S\) and \(S=S^{-1}\). If \(g\) were joined to itself, then \(g=gs\) for some \(s\in S\). Multiplying on the left by \(g^{-1}\) gives \(e=s\), contrary to \(e\notin S\). Thus there are no loops. If \(g\) is joined to \(gs\), then \(s^{-1}\in S\), and \((gs)s^{-1}=g\). Hence the same relation joins \(gs\) back to \(g\), so adjacency is undirected. The construction uses unordered pairs as edges, so repeated descriptions of a pair give just one edge, as required in a simple graph.
Conversely, suppose the relation gives a simple undirected graph. If \(e\in S\), then \(g\) is joined to \(ge=g\) for every \(g\in G\), producing a loop. Simplicity rules this out, so \(e\notin S\). Now take any \(s\in S\). The relation joins \(e\) to \(s\). Since the graph is undirected, it also joins \(s\) to \(e\). By the definition of the relation, \(e=st\) for some \(t\in S\). Multiplying on the left by \(s^{-1}\) gives \(t=s^{-1}\). Therefore \(s^{-1}\in S\), for each \(s\in S\), and \(S=S^{-1}\). Both conditions are necessary and sufficient. \(\square\)
When these conditions hold, each vertex has exactly \(|S|\) neighbors. Indeed, the neighbors of \(g\) are the elements \(gs\) for \(s\in S\). If \(gs=gt\), multiplication on the left by \(g^{-1}\) gives \(s=t\), so different elements of \(S\) give different neighbors. Also, \(gs\ne g\) because \(e\notin S\). Thus the Cayley graph is \(|S|\)-regular. This counts neighbors, not directed arcs: each undirected edge is incident to two vertices.
If \(e\in S\), loops result; if \(S\ne S^{-1}\), the relation may be directed rather than undirected. One can define a different undirected graph using \(S\cup S^{-1}\), but that replaces the proposed steps by a new set. It is not the same construction with the original \(S\).
Worked Examples in the Quaternion Group
We will use the quaternion group \(Q_8=\{1,-1,i,-i,j,-j,k,-k\}\). Its multiplication is determined by \(i^2=j^2=k^2=-1\), \(ij=k\), \(jk=i\), \(ki=j\), and reversing the order in any of the last three products changes the sign. The elements \(1\) and \(-1\) multiply as scalar signs, and multiplication is associative. This explicit description is enough to calculate the steps used below.
Worked Example: A Cayley Graph with Inverse-Closed Steps
Take \(G=Q_8\) and \(S=\{i,-i,j,-j\}\). The identity is not in \(S\). Since \(i^{-1}=-i\) and \(j^{-1}=-j\), the set is inverse-closed, so it defines a simple undirected graph. The vertices are the eight listed group elements. To construct its adjacencies, multiply each vertex on the right by each of the four elements of \(S\):
| Vertex \(g\) | Neighbors \(gi,g(-i),gj,g(-j)\) |
|---|---|
| \(1\) | \(i,-i,j,-j\) |
| \(-1\) | \(-i,i,-j,j\) |
| \(i\) | \(-1,1,k,-k\) |
| \(-i\) | \(1,-1,-k,k\) |
| \(j\) | \(-k,k,-1,1\) |
| \(-j\) | \(k,-k,1,-1\) |
| \(k\) | \(j,-j,-i,i\) |
| \(-k\) | \(-j,j,i,-i\) |
For example, the row for \(i\) follows from \(ii=-1\), \(i(-i)=1\), \(ij=k\), and \(i(-j)=-k\). Each row has four distinct neighbors. As a check, the row for \(i\) lists \(1\) and \(-1\), and the row for \(1\) lists \(i\), while the row for \(-1\) also lists \(i\); these are the reverse descriptions required for undirected edges.
The degree sum is \(8\cdot4=32\), so the number of undirected edges is \(32/2=16\). Independently, count the unordered pairs directly from the table: the rows for \(1,-1\) contribute \(4+4\) distinct pairs; the row for \(i\) adds \(2\) pairs not yet counted, and the row for \(-i\) adds \(2\); the rows for \(j,-j\) add \(2+2\); the rows for \(k,-k\) add none because those pairs have already appeared. The total is \(4+4+2+2+2+2=16\).
Worked Example: A Valid but Disconnected Cayley Graph
Keep \(G=Q_8\), but now use \(S=\{-1\}\). Its only element is not the identity, and \((-1)^{-1}=-1\), so this also defines a simple undirected Cayley graph. Right multiplication by \(-1\) changes the sign of every vertex: the edges are \(\{1,-1\}\), \(\{i,-i\}\), \(\{j,-j\}\), and \(\{k,-k\}\).
Every vertex has one neighbor, and the four listed edges have disjoint endpoints. Thus the graph has four components, each consisting of one edge. The set \(\{-1\}\) generates only the subgroup \(\{1,-1\}\), not all eight elements of \(Q_8\). This example satisfies the conditions for a simple undirected graph, but it is disconnected.
Check: the edge list covers all eight vertices exactly once, so it indeed gives four components. The degree sum is \(8\cdot1=8\), corresponding to \(8/2=4\) edges, in agreement with the list.
Worked Example: What Fails Without Inverse Closure
Again take \(G=Q_8\), now with \(S=\{i,j\}\). Neither step is the identity, but \(i^{-1}=-i\notin S\) and \(j^{-1}=-j\notin S\). The relation includes the step from \(1\) to \(i\), since \(1\cdot i=i\). For the reverse step to be present, multiplication from \(i\) would have to reach \(1\); the required multiplier is \(i^{-1}=-i\), which is absent. Hence the relation is not undirected.
For a concrete calculation, the outgoing neighbors of \(1\) are \(i,j\), while the outgoing neighbors of \(i\) are \(i^2=-1\) and \(ij=k\). In particular, \(1\) is not an outgoing neighbor of \(i\). The relation can be treated as a directed relation, but it is not a simple undirected Cayley graph under the stated definition.
Check: \(i(-i)=1\), so \(-i\) is exactly the step needed to reverse \(1\to i\); because \(-i\notin\{i,j\}\), the reverse step is indeed missing.
Generation and Connectedness
Proof. Suppose first that the graph is connected. For any \(g\in G\), there is a path from \(e\) to \(g\). At each step, the current vertex \(x\) is replaced by \(xs\) for some \(s\in S\). If the path uses the steps \(s_1,\ldots,s_\ell\), its successive vertices are \(e,s_1,s_1s_2,\ldots,s_1s_2\cdots s_\ell\). Its endpoint is therefore \(g=s_1s_2\cdots s_\ell\), a product of elements of \(S\). This holds for every \(g\), so \(S\) generates \(G\).
Conversely, suppose \(S\) generates \(G\). For any \(g\in G\), write \(g=s_1s_2\cdots s_\ell\), where each \(s_r\in S\). Starting at \(e\), successively multiply on the right by \(s_1,s_2,\ldots,s_\ell\). The resulting sequence begins at \(e\), ends at \(g\), and each consecutive pair is adjacent by the definition of the Cayley graph. Thus every vertex is reachable from \(e\). For any \(x,y\in G\), a path from \(e\) to \(x^{-1}y\) can be left-multiplied by \(x\): each step from \(z\) to \(zs\) becomes a step from \(xz\) to \((xz)s\), still an edge. This gives a path from \(x\) to \(y\). Hence the graph is connected. The argument also covers the trivial group: its sole vertex is connected to itself by a path of length zero, and the empty set generates it. \(\square\)
The proof describes what generation means in the graph: a word in the permitted steps gives a walk from the identity to its product. Inverse closure ensures that each step can also be traversed in reverse. A set can therefore define a valid Cayley graph without making that graph connected, as the second example showed.
Common Pitfall: Reversing a Step
A frequent error is to assume that an edge from \(g\) to \(gs\) automatically gives an edge back from \(gs\) to \(g\). That is true only if \(s^{-1}\) is also an allowed step. For instance, with \(S=\{i,j\}\) in \(Q_8\), the forward calculation is \(1\cdot i=i\), but the reverse calculation requires \(i\cdot(-i)=1\). Using \(i\) instead gives \(i\cdot i=-1\), not \(1\). The correction is to test the inverse of every proposed step: an undirected Cayley graph requires \(s^{-1}\in S\) for every \(s\in S\), as well as \(e\notin S\).
Keep three questions separate when constructing a graph: what are its vertices, what are the allowed multiplication steps, and do those steps meet the conditions for an undirected simple graph? Only after checking those conditions should one infer properties such as regularity or connectedness. Regularity follows from the distinct neighbors \(gs\), while connectedness additionally requires that the steps generate the whole group.
Check Your Understanding
Use right multiplication throughout, and state the condition that justifies each conclusion.
- For a finite group \(G\), why does including \(e\) in \(S\) create a loop?
- In \(Q_8\), calculate the neighbors of \(-i\) when \(S=\{i,-i,j,-j\}\).
- Explain why \(S=\{-1\}\) defines a simple undirected Cayley graph on \(Q_8\) but does not give a connected graph.
- Suppose \(S=S^{-1}\), \(e\notin S\), and \(|S|=r\). Prove directly that every vertex has degree \(r\).
- For a path from \(e\) whose successive right-multiplication steps are \(s_1,s_2,s_3\), write its endpoint and explain why it belongs to the subgroup generated by \(S\).