The circumference of a hypercube graph

Question

How can I find the circumference of a hypercube graph? is easy to see that a n-dimensional hypercube have a $2n$-cycle, but I cant prove that it's the largest, can anybody help me?

Answer 1

The longest cycle is always bounded by the number of vertices, by definition of a cycle. So in this case the longest cycle is bounded above by $2^n$.

Edit: So if can show that a cycle of length $2^n$ always exists then likewise the circumference must be $2^n$. As the comment below says the proof is by induction.

Each $v \in Q_n$ can be represented by a binary string such that $v \in \{ 0 ,1 \}^n$. Only pairs of vertices with binary representations that differ by a single binary digit are connected by an edge.

For the base case $n=2$ we have the path $00 \rightarrow 01 \rightarrow 11 \rightarrow 10 \rightarrow 00$.

Then for the inductive step assume that $Q_{n-1}$ has a Hamilton circuit. Let $v$ be any neighbor of $0^{n-1}$ (the sequence of $n-1$ $0$s) and delete the edge connecting $0^{n-1}$ to $v$. Now we have a path, $P$ through every vertex of $Q_{n-1}$. We orient the path to go from $0^{n-1}$ to $v$, and denote $P^{-1}$ as the path oriented in reverse. We let the $+$ symbol represent concatenation so that, for example, $0 + 0 = 00$, and where $0 + P$ concatenates each $v \in P$. Then a Hamiltonian circuit in $Q_n$ is given by, $0 + P \rightarrow 1 + P^{-1} \rightarrow 0^n$.

Therefore the circumference of $Q_n$ for $n \geq 2$ is $2^n$.