The Hypercube as a Cayley Graph

Binary Strings as Group Elements

The hypercube has a simple adjacency rule: two binary strings are adjacent when they differ in exactly one coordinate. A group description turns that rule into a uniform operation: from any string, add one of a fixed set of generators. This makes the hypercube a concrete example of a Cayley graph and connects coordinate changes with algebraic structure.

Fix an integer \(n\ge 0\). Let \(B_n\) be the set of all binary strings of length \(n\), viewed as vectors \(x=(x_1,\ldots,x_n)\) with \(x_i\in\{0,1\}\). Define addition coordinatewise modulo two. Thus \(0+0=0\), \(0+1=1\), \(1+0=1\), and \(1+1=0\) in each coordinate. The identity is the all-zero string \(0^n\), and every element is its own inverse: \(x+x=0^n\). With this operation \(B_n\) is an abelian group, called the Boolean group of order \(2^n\).

For \(1\le i\le n\), let \(e_i\) be the string with a \(1\) in coordinate \(i\) and \(0\) in every other coordinate. Adding \(e_i\) to \(x\) changes exactly its \(i\)th coordinate. The set \(S_n=\{e_1,\ldots,e_n\}\) is the standard generating set. When \(n=0\), the string is empty, \(B_0\) contains just that string, and \(S_0\) is empty.

The Hypercube Representation

Proof. Both graphs have the same vertex set \(B_n\). In the Cayley graph, \(x\) is adjacent to \(y\) exactly when \(y=x+e_i\) for some \(i\). Since \(x+x=0^n\), this is equivalent to \(x+y=e_i\). Adding \(e_i\) flips coordinate \(i\) and leaves every other coordinate unchanged, so this condition holds exactly when \(x\) and \(y\) differ in one coordinate. That is precisely the defining adjacency condition for \(Q_n\). When \(n=0\), there are no generators and no edges, and both graphs consist of the single empty string. Thus the graphs agree for all \(n\ge0\). \(\square\)

The choice of generators matters. Each \(e_i\) describes one allowed move, not an arbitrary change of string. Also, the graph is simple: no generator is \(0^n\), so there are no loops; and if \(x+e_i=x+e_j\), adding \(x\) to both sides gives \(e_i=e_j\), so \(i=j\) and there are no repeated neighbors from different generators.

Consequences of the Generator Description

For \(n\ge1\), the standard generators are distinct, and adding \(e_i\) to a fixed vertex gives a different neighbor for each \(i\). Hence every vertex has degree \(n\), so \(Q_n\) is \(n\)-regular. Each string is a sum of the standard generators: \(x=\sum_{i:x_i=1}e_i\). Consequently, one can reach any vertex \(x\) from \(0^n\) by adding the generators corresponding to its \(1\)-coordinates. The graph is connected; for \(n=0\), it is connected as a single-vertex graph.

The number of vertices is \(2^n\), since each of the \(n\) coordinates has two choices. For \(n\ge1\), the handshake lemma says that the sum of the degrees is twice the number of edges. Applying it to this \(n\)-regular graph gives the edge count below. The exceptional case \(n=0\) has no edges.

The algebra also describes distance. Define the Hamming weight \(\operatorname{wt}(z)\) to be the number of coordinates of \(z\) equal to \(1\). The Hamming distance between \(x\) and \(y\) is \(\operatorname{wt}(x+y)\), because a coordinate of \(x+y\) is \(1\) exactly where \(x\) and \(y\) differ.

Proof. Let \(k=\operatorname{wt}(x+y)\). The strings differ in exactly \(k\) coordinates. Flipping each of those coordinates once gives a path from \(x\) to \(y\) of length \(k\), so their graph distance is at most \(k\). Conversely, each edge flips exactly one coordinate. To get from \(x\) to \(y\), each of the \(k\) differing coordinates must be flipped an odd number of times, and therefore at least once. Any such path has length at least \(k\). The two inequalities give distance \(k\). If \(x=y\), then \(k=0\), and the length-zero path gives the same conclusion. \(\square\)

Why the Boolean Group Is the Right One

The group operation records the effect of coordinate changes without requiring separate rules for every starting vertex. Adding the same generator at any vertex performs the same coordinate flip. Moreover, adding a string \(a\) to every vertex preserves adjacency: if \(y=x+e_i\), then \(y+a=(x+a)+e_i\). Thus translations \(x\mapsto x+a\) preserve the hypercube's edges. This illustrates how the Cayley graph description exposes symmetries through the group operation.

There is a useful distinction between the generating set and the group itself. The group \(B_n\) contains all \(2^n\) strings, but the standard generating set contains only the \(n\) strings with exactly one \(1\). A move in the graph adds one generator, not any group element. Several moves may combine to add a string with multiple \(1\)-coordinates.

Common Pitfall: Using Too Many Generators

For \(n=2\), an incorrect choice would be \(S=\{01,10,11\}\), the set of all nonzero elements of \(B_2\). This makes \(00\) adjacent to \(11\), since \(00+11=11\in S\). But \(00\) and \(11\) differ in two coordinates, so that edge is not in the square \(Q_2\). The correct generating set is only \(\{01,10\}\): \(11\) is reached from \(00\) by two moves, because \(00+01=01\) and \(01+10=11\). Including \(11\) as a generator changes the graph rather than describing the hypercube.

Another potential confusion is ordinary integer addition. In \(B_n\), addition is coordinatewise modulo two, with no carrying between coordinates. For example, \(01+01=00\), not the binary representation of the ordinary integer \(2\). The coordinatewise rule is what makes every generator a single-coordinate flip.