Prove hypercube is hamiltonian

In this article, we will prove that every hypercube is hamiltonian.

Hamiltonian: A graph is Hamiltonian if it contains a Hamiltonian circuit. It means there exists a cycle in the graph that visits each vertex exactly once.

Hypercube: It is denoted by Qn. It contains 2n vertices and the degree of each vertex is n.
Each vertex is assigned a distinct number in range 0 to 2n – 1. Two vertices are connected only if they differ by exactly one bit ( hamming distance between the vertices is one ).

hypercube

Proof hypercube is hamiltonian

The proof is very simple. It is based on the fact that vertices connected to each other differ by exactly one bit.

Suppose a hypercube Qn. Create a Gray Code sequence of n-bits. Gray Code is the ordering such that two successive numbers differ by exactly one bit. Gray Code includes all numbers in the range [ 0, 2n – 1 ] exactly once. That means if we traverse the graph by Gray Code ordering, we can traverse all the vertices without repetition.

The gray code always starts with 000…0 (n times 0) and ends at 100..0 (1 followed by n-1 0’s). The first and last number in the gray code sequence also differs by 1-bit. Therefore, there exists an edge between the first and last vertex. Thus, a cycle is formed.

The cycle formed by traversing vertices in gray code order visits all vertices exactly once. Thus, it is a Hamiltonian circuit. Therefore, every hypercube is Hamiltonian.

For example,

Suppose hypercube Q3.
The gray code ordering of vertices is

000 (0)
001 (1)
011 (3)
010 (2)
110 (6)
111 (7)
101 (5)
100 (4)

All adjacent numbers differ by exactly one bit. The last and first numbers also differ by one bit. Thus, the above sequence forms a Hamiltonian circuit.

Hamiltonian circuit in hypercube Q3

Read
Prove that Hypercube is Bipartite

References
n-bit Gray Code

Leave a Comment

Your email address will not be published. Required fields are marked *