# n-Cube as a Cayley Graph

I'm taking a class on graph theory that uses "Graph Theory (Graduate Texts in Mathematics)" by Bondy and Murty. One of the questions is about Cayley graphs and the n-cube, and I don't understand how to interpret it. It runs as follows:

Let $\Gamma$ be a group and $S$ be a subset of $\Gamma$ not including the identity element. Suppose that the inverse of every element in $S$ also belongs to $S$. The Cayley graph of $\Gamma$ with respect to $S$ is the graph $CG(\Gamma, S)$ with vertex set $\Gamma$ in which two vertices $x$ and $y$ are adjacent iff $xy^{-1}\in S$.

Recall that the n-cube is the graph whose vertex set is the set of all n-tuples of 0s and 1s, where two n-tuples are adjacent if they differ in precisely one coordinate.

Makes sense.

Show that the n-cube is a Cayley graph.

What does it mean to talk about "$xy$" when $x$ and $y$ are n-tuples? What is the inverse of an n-tuple?

Someone I asked about the problem suggested that I treat $\Gamma$ here as the additive group $({\mathbb Z}/2{\mathbb Z})^n$, and so take $xy^{-1}$ to mean elementwise subtraction of $y$ from $x$, mod 2. But then it seems like $(0, 0, ..., 0)\in\Gamma$ and, since it's the identity element, every vertex will have an edge connecting to it, and that isn't what the n-cube looks like. Googling, I also see that there is an interpretation of tuples as nested sets, but then I don't see how the product of two nested sets would ever be in S, since it will have a different cardinality from either of the original tuples. Interpreting the tuples as vectors can't work either since then $xy^{-1}$ will have different dimensions than either of the original tuples.

• If every vertex has an edge connecting to (0,0,...,0), then every non-identity element is in S. $\hspace{1.01 in}$ – user12859 Apr 13 '14 at 3:30
• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Apr 13 '14 at 8:23

The question is asking you to find a suitable group $\Gamma$ and a subset $S$, so that $CG(\Gamma,S)$ is the n-cube.
Since by definition of $CG$, the nodes are the elements of $\Gamma$, you don't have a choice here, leaving the group operation and $S$.
$xy$ and the inverse of $y$ are then understood with respect to the group operation you choose.
Also be aware that the identity element being in $\Gamma$ does not imply that all other vertices are connected with it, since the edges are determined by $S$, not $\Gamma$.
• Okay, so any $\Gamma$ will work? In particular, I could, say, call $\Gamma$ the set of all n-bit integers, define the group operation to be XOR, and let $S$ be all of the powers of two, from 0 to $n$? And provide a mapping from n-element tuples to n-bit integers to show that they're equivalent? – Patrick Collins Apr 13 '14 at 19:27