Introduction to Graph Theory · Problem 2.23

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · hamiltonian-cycles-hypercube-variants

Problem

Let

n

and

k

be two integers such that

n > k > 0

. Define the simple graph

Q_{n,k}

as follows: Its vertices are the bitstrings

(a_1, a_2, \ldots, a_n) \in \{0,1\}^n

; two such bitstrings are adjacent if and only if they differ in exactly

k

bits (in other words: two vertices

(a_1, a_2, \ldots, a_n)

and

(b_1, b_2, \ldots, b_n)

are adjacent if and only if the number of

i \in \{1, 2, \ldots, n\}

satisfying

a_i \neq b_i

equals

k

). (Thus,

Q_{n,1}

is the

n

-hypercube graph

Q_n

.) (a) Does

Q_{n,k}

have a hamc when

k

is even? (Recall that ``hamc'' is short for ``Hamiltonian cycle''.) (b) Does

Q_{n,k}

have a hamc when

k

is odd? [Hint: One way to approach part (b) is by identifying the set

\{0,1\}

with the field

\mathbb{F}_2

with two elements. The bitstrings

(a_1, a_2, \ldots, a_n) \in \{0,1\}^n

thus become the size-

n

row vectors in the

\mathbb{F}_2

-vector space

\mathbb{F}_2^n

. Let

e_1, e_2, \ldots, e_n

be the standard basis vectors of

\mathbb{F}_2^n

(so that

e_i

has a

1

in its

i

-th position and zeroes everywhere else). Then, two vectors are adjacent in the

n

-hypercube graph

Q_n

(resp. in the graph

Q_{n,k}

) if and only if their difference is one of the standard basis vectors (resp., a sum of

k

distinct standard basis vectors). Try to use this to find a graph isomorphism from

Q_n

to a subgraph of

Q_{n,k}

Intuitive explanation

The key insight is to use a parity argument combined with a bipartite structure hidden in the graph. Think of each bitstring as a vector in $\mathbb{F}_2^n$ , and notice that moving from one vertex to an adjacent vertex changes the Hamming weight (number of 1's) by exactly $k$ . When $k$ is even, this preserves parity of the weight; when $k$ is odd, it flips parity. A Hamiltonian cycle must visit all $2^n$ vertices, and the parity constraint becomes a topological obstruction that either allows or forbids such a cycle depending on whether $k$ is even or odd.

Intuitive explanation

Browse the problem library