Hypercube graph

In graph theory, the hypercube graph Q_n is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^n – 1n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n 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 Q_n – 1 connected to each other by a perfect matching. Hypercube graphs should not be confused with cubic graphs, which are graphs that have exactly three edges touching each vertex. The only hypercube graph Q_n that is a cubic graph is the cubical graph Q_3. 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.