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$.Okay. I follow so far.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.What is this question asking?
n-Cube as a Cayley Graph
graph theory;terminology;group theory
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$.