Draw a hypercube graph Q₃ (also called the cubical hypercube). Check whether the hypercube Q₃ is Hamiltonian.

Answer: $Q_3$ is Hamiltonian, with a Hamiltonian cycle given by $000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$ .

Step-by-step solution

Step 1: Define the hypercube graph $Q_3$

The hypercube graph $Q_3$ consists of $8$ vertices corresponding to all binary strings of length $3$ . Two vertices are connected by an edge if and only if their binary strings differ by exactly $1$ bit. Each vertex has degree $3$ , making it a $3$ -regular bipartite graph with $12$ edges in total.

Step 2: Recall the definition of a Hamiltonian graph

A graph is Hamiltonian if it contains a Hamiltonian cycle, which is a closed walk that visits every vertex in the graph exactly once before returning to the starting vertex. For $Q_3$ , such a cycle must have length $8$ .

Step 3: Construct a Hamiltonian cycle using a Gray code

A standard $3$ -bit Gray code sequence visits all $8$ binary vectors such that consecutive vectors differ by only $1$ bit, with the last vector also differing from the first by $1$ bit. Translating this Gray code gives the cycle $000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$ , which is a valid cycle of length $8$ in $Q_3$ .

Step 4: Conclude Hamiltonian property

Since we have explicitly found a cycle that visits all $8$ vertices of $Q_3$ without repetition and returns to the start, $Q_3$ contains a Hamiltonian cycle. More generally, every hypercube graph $Q_n$ for $n \ge 2$ is Hamiltonian.

Solve your own maths question free →