Hypercube graphs
Share
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.
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
0000and1111, 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
- Hypercube graph, Wikipedia: en.wikipedia.org
- Hypercube Graph, Wolfram MathWorld: mathworld.wolfram.com
- NetworkX
hypercube_graph: networkx.org - Gray code, Wikipedia: en.wikipedia.org
- C. L. Seitz, "The Cosmic Cube," Communications of the ACM 28(1), 1985.
- W. D. Hillis, The Connection Machine, MIT Press, 1985.