Hypercube Graphs From Binary Strings

Binary Strings as Vertices

A cube graph can be described without relying on a drawing: label each vertex by a binary string, then join strings that differ in exactly one position. This gives a precise way to construct the graph in any dimension. In low dimensions, writing out the strings and checking their coordinates gives a practical way to produce a complete edge list.

Fix a nonnegative integer \(n\). A binary string of length \(n\) is a sequence of \(n\) entries, each either \(0\) or \(1\). For two strings of the same length, their differing-coordinate count is the number of positions at which their entries are unequal. The length-zero string is denoted by \(\varepsilon\); there is just one such string.

Definition: The n-dimensional cube graph \(Q_n\) is the simple graph whose vertices are all binary strings of length \(n\). Two distinct vertices are adjacent exactly when their strings differ in one coordinate. In particular, \(Q_0\) has vertex set \(\{\varepsilon\}\) and no edges.

When listing edges, we write an edge as an unordered pair of strings, such as \(\{00,01\}\). The order of the strings in such a pair does not matter. A useful way to organize an edge list is by the coordinate in which the two endpoints differ. Every edge belongs to exactly one such group: its endpoints differ in one coordinate, and that coordinate is unique.

Constructing the First Cube Graphs

Worked Example: The One-Dimensional Cube

There are two binary strings of length one, \(0\) and \(1\). They differ in their only coordinate, so the complete graph specification is

V(Q_1)=\{0,1\},\qquad E(Q_1)=\bigl\{\{0,1\}\bigr\}.

There are no other possible pairs of distinct vertices: the displayed pair is the only one. Thus the edge list is complete. The graph has two vertices and one edge, as is also confirmed directly by counting the displayed vertex and edge sets.

Worked Example: The Two-Dimensional Cube

List the binary strings of length two in lexicographic order: \(00,01,10,11\). To find the edges, compare pairs and keep exactly those that differ in one coordinate. Grouping by the differing coordinate gives the full specification

\begin{aligned} V(Q_2)&=\{00,01,10,11\},\\ E(Q_2)&=\bigl\{ \{00,10\},\{01,11\}, \{00,01\},\{10,11\} \bigr\}. \end{aligned}

The first two listed edges differ in the first coordinate; the last two differ in the second. Each possible edge must differ in exactly one of the two positions, so these groups include every edge allowed by the definition. They do not overlap, since a pair differing in the first position cannot also differ in the second.

Check: there are four listed vertices and four listed edges. Independently, fixing the first coordinate as the differing one gives two pairs, \(\{00,10\}\) and \(\{01,11\}\); fixing the second gives two pairs, \(\{00,01\}\) and \(\{10,11\}\). The groups are disjoint, so the count is \(2+2=4\) edges, agreeing with the edge list.

Worked Example: The Three-Dimensional Cube

List all length-three strings. For each coordinate, hold the other two coordinates fixed and change the chosen coordinate from \(0\) to \(1\). This generates exactly the pairs differing in that coordinate:

\begin{aligned} V(Q_3)={}&\{000,001,010,011,100,101,110,111\},\\ E(Q_3)={}&\bigl\{ \{000,100\},\{001,101\},\{010,110\},\{011,111\},\\ &\quad\{000,010\},\{001,011\},\{100,110\},\{101,111\},\\ &\quad\{000,001\},\{010,011\},\{100,101\},\{110,111\} \bigr\}. \end{aligned}

The first group of four edges differs in the first coordinate, the second group of four in the second coordinate, and the third group of four in the third coordinate. For each group, the two unchanged coordinates can be chosen in four ways, producing the four displayed pairs. Each pair differs in exactly its group’s coordinate, so it is an edge; and every edge must differ in one of the three coordinates, so the groups exhaust the edge set. Since an edge has a unique differing coordinate, no edge is repeated across groups.

Check: the vertex list contains eight strings, and the edge list has \(4+4+4=12\) pairs. The count in each coordinate group is four because there are four assignments to the two unchanged positions. Summing the disjoint groups gives twelve edges, independently confirming the list’s size.

Why the Construction Lists Every Vertex and Edge

Proposition: For every nonnegative integer \(n\), \(Q_n\) has \(2^n\) vertices. For \(n\geq 1\), its edges split into \(n\) disjoint coordinate groups, each containing \(2^{n-1}\) edges. Consequently, \(Q_n\) has \(n2^{n-1}\) edges when \(n\geq 1\); \(Q_0\) has no edges.

Proof. Each of the \(n\) positions in a binary string can be filled in two ways, independently of the other positions. Therefore there are \(2^n\) strings, which are exactly the vertices of \(Q_n\). This reasoning also includes \(n=0\): there is one choice of string, the empty string, and \(2^0=1\).

Now suppose \(n\geq1\), and fix a coordinate \(i\). To form an edge differing in coordinate \(i\), choose the entries in the other \(n-1\) positions freely. There are \(2^{n-1}\) such assignments. For each assignment there is exactly one edge: its two endpoints have those same entries in the other positions, and have \(0\) and \(1\) in position \(i\). Conversely, every edge differing in position \(i\) comes from exactly this assignment to the other positions. Thus the group for coordinate \(i\) contains \(2^{n-1}\) edges.

Every edge differs in exactly one coordinate, so it belongs to one coordinate group, not more than one. The \(n\) groups are disjoint, and adding their sizes gives \(n2^{n-1}\). The argument requires \(n\geq1\) for the edge count; the separately defined graph \(Q_0\) has one vertex and no possible edge. \(\square\)

This count is a completeness check, not a substitute for listing the edges when a full list is required. In a small example, organize the proposed list by coordinate and compare the number of pairs in each group with the number of assignments to the remaining coordinates. That checks both that no permitted pair is missing and that no pair has been included twice.

A Recursive Construction

Theorem: For \(n\geq1\), \(Q_n\) can be constructed from two copies of \(Q_{n-1}\) by prefixing every string in one copy with \(0\), prefixing every string in the other copy with \(1\), and joining each pair of corresponding strings with an edge.

Proof. Consider all length-\(n\) strings in \(Q_n\). Those beginning with \(0\) have the form \(0x\), where \(x\) is a binary string of length \(n-1\); those beginning with \(1\) have the form \(1x\). These two sets are disjoint and together contain every vertex. Within either set, two strings are adjacent exactly when their suffixes differ in one coordinate. Thus the edges within each set are precisely a copy of the edges of \(Q_{n-1}\), with a fixed prefix added.

It remains to identify edges between the two sets. A string \(0x\) and a string \(1y\) already differ in their first coordinate. They differ in exactly one coordinate overall if and only if \(x=y\). Therefore the edges between the sets are exactly the pairs \(\{0x,1x\}\), one for each length-\((n-1)\) string \(x\). These are the corresponding-vertex edges in the stated construction. The within-set and between-set cases cover all possible edges, so the construction gives precisely \(Q_n\). \(\square\)

The theorem gives a second way to build edge lists. First list the edges within each prefixed copy; then list the corresponding-string pairs between copies. In particular, starting with \(Q_0\), the first step gives two single vertices and their connecting edge, which is \(Q_1\). Repeating the construction creates successively longer strings while keeping track of where each edge comes from.

Worked Example: Building \(Q_2\) from Two Copies of \(Q_1\)

The two copies have vertex sets \(\{00,01\}\) and \(\{10,11\}\): these result from prefixing the vertices \(0,1\) of \(Q_1\) with \(0\) and \(1\), respectively. The within-copy edges are \(\{00,01\}\) and \(\{10,11\}\). The corresponding strings \(0\) and \(0\), then \(1\) and \(1\), give the between-copy edges \(\{00,10\}\) and \(\{01,11\}\).

Thus the recursive construction produces \(V=\{00,01,10,11\}\) and \(E=\{\{00,01\},\{10,11\},\{00,10\},\{01,11\}\}\). Each listed pair differs in one position. Conversely, the two edges within copies account for pairs with equal first coordinate, while the two between-copy edges account for pairs with different first coordinate and equal second coordinate. Hence no other pair is an edge. This agrees with the direct coordinate-by-coordinate construction of \(Q_2\).

Common Pitfall: Omitting the Edges Between Copies

A common incomplete construction takes two smaller cubes and includes only the edges within each copy. For example, taking two copies of \(Q_2\) produces eight internal edges: each copy has four edges, so the internal total is \(4+4=8\). But that is not yet \(Q_3\). The copies have prefixes \(0\) and \(1\), and each length-two suffix must be joined to its counterpart in the other copy. There are four such suffixes, so four between-copy edges must be added. The complete total is \(8+4=12\), matching the three-coordinate count \(4+4+4=12\).

The correction is to check how an edge can differ: it either lies within one prefix group, where the suffixes differ in one position, or connects the two prefix groups, where the suffixes must be identical. Applying both cases prevents the missing-edge error. The same two-case check works in every dimension.

Check Your Understanding

Use the binary-string definition and show enough of your construction to make each answer verifiable.

Write the complete vertex and edge sets of \(Q_0\) and \(Q_1\). Explain why the length-zero case has no edges.
For \(Q_2\), group the edges by differing coordinate and check that every listed pair differs in exactly one position.
Construct the vertex set of \(Q_3\), then organize its edges into coordinate groups. Explain why the groups cannot repeat an edge.
Use the recursive construction to describe the two copies and the between-copy edges in \(Q_3\), starting from \(Q_2\).
Explain why counting the strings that agree outside a fixed coordinate gives the number of edges in that coordinate group.