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 **Q _{n}**. It contains

**2**vertices and the degree of each vertex is

^{n}**n**.

Each vertex is assigned a distinct number in range

**0 to 2**. Two vertices are connected only if they differ by exactly one bit ( hamming distance between the vertices is one ).

^{n}– 1## 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 **Q _{n}**. 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, 2**exactly once. That means if we traverse the graph by Gray Code ordering, we can traverse all the vertices without repetition.

^{n}– 1 ]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 Q_{3}.

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.

**Read**

Prove that Hypercube is Bipartite

**References**

n-bit Gray Code