The hypercube graph Qn may also be constructed by creating a vertex for each subset of an n-element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n-digit binary number, with two vertices adjacent when their binary representations differ in a single digit.

It is the n-fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of Qn – 1 connected to each other by a perfect matching.

The hypercube graph Qn may be constructed from the family of subsets of a set with n elements, by making a vertex for each possible subset and joining two vertices by an edge whenever the corresponding subsets differ in a single element.

Equivalently, it may be constructed using 2n vertices labeled with n-bit binary numbers and connecting two vertices by an edge whenever the Hamming distance of their labels is one.

These two constructions are closely related: a binary number may be interpreted as a set (the set of positions where it has a 1 digit), and two such sets differ in a single element whenever the corresponding two binary numbers have Hamming distance one.

Alternatively, Qn may be constructed from the disjoint union of two hypercubes Qn − 1, by adding an edge from each vertex in one copy of Qn − 1 to the corresponding vertex in the other copy, as shown in the figure.

The joining edges form a perfect matching.

Another construction of Qn is the Cartesian product of n two-vertex complete graphs K2.

Additionally, a Hamiltonian path exists between two vertices u and v if and only if they have different colors in a 2-coloring of the graph.

Hamiltonicity of the hypercube is tightly related to the theory of Gray codes.

More precisely there is a bijective correspondence between the set of n-bit cyclic Gray codes and the set of Hamiltonian cycles in the hypercube Qn.

[2] An analogous property holds for acyclic n-bit Gray codes and Hamiltonian paths.

A lesser known fact is that every perfect matching in the hypercube extends to a Hamiltonian cycle.

[3] The question whether every matching extends to a Hamiltonian cycle remains an open problem.

The problem of finding the longest path or cycle that is an induced subgraph of a given hypercube graph is known as the snake-in-the-box problem.

Szymanski's conjecture concerns the suitability of a hypercube as a network topology for communications.

It states that, no matter how one chooses a permutation connecting each hypercube vertex to another vertex with which it should be connected, there is always a way to connect these pairs of vertices by paths that do not share any directed edge.