Hypercube graph

In the mathematical field of graph theory, the hypercube graph $Q_{n}$ is a special regular graph with $2^{n}$ vertices, which correspond to the subsets of a set with n elements. Two vertices labelled by subsets S and T are joined by an edge if and only if S can be obtained from T by adding or removing a single element. Each vertex of a hypercube is incident to exactly n edges, so that the total number of edges is $2^{n-1}n$.

The vertices of a hypercube can be regarded as strings of n bits. In this labeling, two bit strings represent adjacent vertices if and only if they agree in exactly $n-1$ positions. The hypercube can also be defined as the Hasse diagram of a Boolean algebra, or as the one-dimensional skeleton of a measure polytope.

For example, the graph $Q_{0}$ consists of a single vertex, while $Q_{1}$ is the complete graph on two vertices and $Q_{2}$ is a cycle of length 4.

Every hypercube is a bipartite graph, because two subsets S and T can represent adjacent vertices only if S has odd cardinality and T"' has even cardinality, or vice versa.

The graph $Q_{n}$ is planar if and only if $n\leq e$.

The hypercubes should not be confused with cubic graphs; only $Q_{3}$ is cubic.