Hypercube graphs

A hypercube graph Qn has one vertex for every string of n bits, and an edge between two strings whenever they differ in exactly one bit. Q1 is a single edge, Q2 is a square, Q3 is the cube, and Q4 is the tesseract, the 4-dimensional hypercube drawn as a cube inside a cube.

The cube graph Q3, with vertices labelled by 3-bit strings A cube drawn in perspective. The front face is labelled 000, 100, 110 and 010. The back face is labelled 001, 101, 111 and 011. Every edge joins two labels that differ in exactly one bit. 000 100 010 110 001 101 011 111
The cube graph Q3: eight vertices, twelve edges. Each edge flips exactly one bit in the label.

That one rule (flip one bit, move along one edge) is why the hypercube shows up everywhere from parallel computers to error-correcting codes to the GPU all-reduce in a training job.

How to build one: doubling

You don't need to picture four dimensions. Take two copies of Qn−1, put a 0 in front of every label in the first copy and a 1 in front of every label in the second, then join each vertex to its twin. That's Qn.

  • Q1: 0 — 1
  • Q2: two edges, joined: the square 00, 01, 11, 10
  • Q3: two squares, joined corner to corner: the cube
  • Q4: two cubes, joined corner to corner: the tesseract

Our hypercube tee is exactly this picture: a square that grew a dimension, then grew another.

Properties

Formula Q3 (cube) Q4 (tesseract) Q6
Vertices 2n 8 16 64
Edges n · 2n−1 12 32 192
Degree (every vertex) n 3 4 6
Diameter n 3 4 6
Shortest cycle (girth), n ≥ 2 4 4 4 4
Bipartite always yes yes yes

Why each one holds:

  • Edges. Every vertex has n neighbours (one per bit you can flip), and each edge is counted from both ends: n · 2n / 2.
  • Distance is Hamming distance. The shortest path between two vertices flips each differing bit once, so the distance is the number of positions where the strings differ. The farthest pair, like 0000 and 1111, is n apart, and there are n! shortest paths between them (one per order in which you flip the bits).
  • Bipartite. Split vertices by whether they have an even or odd number of 1s. Every edge flips one bit, so it always crosses between the two groups. The bipartite graph explainer uses this as its main example.
  • No triangles. Two flips can't undo to one, so the shortest cycle has length 4 (flip bit i, flip bit j, flip i back, flip j back).
  • Hamiltonian. For n ≥ 2 there's a cycle through every vertex exactly once: the Gray code, where consecutive numbers differ by one bit (000, 001, 011, 010, 110, 111, 101, 100).

Compare that with the Petersen graph, which has odd 5-cycles and no Hamiltonian cycle at all.

The tesseract, Q4

The tesseract is Q4: 16 vertices, 32 edges, every vertex of degree 4. The usual drawing is a small cube inside a big cube with each inner corner joined to its outer twin, which is the doubling construction drawn in perspective. (Not to be confused with the Tesseract OCR engine or the Marvel cube.)

Where hypercubes show up

  • Parallel computers. The Caltech Cosmic Cube (1981) linked 64 processors as a 6-dimensional hypercube, and the Connection Machine CM-1 wired its 4,096 router chips as a 12-dimensional hypercube. Any processor reaches any other in at most n hops with only n links each.
  • Collective communication. Recursive-doubling all-reduce, used in MPI and in multi-GPU training, pairs node i with node i XOR 2k in round k: that is walking the edges of a hypercube, one dimension per round.
  • Coding theory. Codewords are vertices of Qn and Hamming distance is graph distance, so an error-correcting code is a set of vertices spread far apart in the hypercube.
  • Boolean functions and logic. The truth table of an n-input function lives on the vertices of Qn; Karnaugh maps are flattened hypercubes.

Python: build and check one in NetworkX

import networkx as nx

n = 4
G = nx.hypercube_graph(n)          # nodes are tuples like (0, 1, 1, 0)

print(G.number_of_nodes())         # 16  = 2**n
print(G.number_of_edges())         # 32  = n * 2**(n-1)
print(set(d for _, d in G.degree()))  # {4}
print(nx.diameter(G))              # 4
print(nx.is_bipartite(G))          # True

# Distance equals Hamming distance
a, b = (0, 0, 0, 0), (1, 0, 1, 1)
print(nx.shortest_path_length(G, a, b))      # 3
print(sum(x != y for x, y in zip(a, b)))     # 3

That nx.hypercube_graph(n) call is the back graphic on the hypercube hoodie.

FAQ

Is a hypercube the same as a tesseract? A tesseract is the 4-dimensional hypercube. "Hypercube" is the general name for any dimension n.

How many edges does an n-dimensional hypercube have? n · 2n−1. The cube has 12, the tesseract 32.

Is the hypercube graph bipartite? Yes, for every n: even-weight and odd-weight bit strings form the two parts. See the bipartite graph explainer.

What is the diameter of Qn? n, the distance between a string and its complement.

Related: the Petersen graph explained, the famous non-Hamiltonian counterexample, and bipartite graphs explained, whose even/odd split is the hypercube's. Or give the cube's edges a direction: directed acyclic graphs explained.

The graph on a shirt

The drawing on the Hypercube Graph Tee – Out of the Box (€45) is this graph: a square that grew a dimension, then grew another. The hypercube hoodie (€85) has the same graph on the chest and G = nx.hypercube_graph(n) on the back. The rest of the line is in the Graphs collection. Buying for a mathematician? See our gifts for mathematicians guide.

Sources

Back to blog