Hypercube graph

Hypercube graph
The hypercube graph Q4
Vertices	2n
Edges	2n−1n
Diameter	n
Girth	4 if n ≥ 2
Automorphisms	n! 2n
Chromatic number	2
Spectrum	${\displaystyle \{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}}$
Properties	Symmetric Distance regular Unit distance Hamiltonian Bipartite
Notation	Qn

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 cubical graph Q₃ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2ⁿ vertices, 2ⁿ⁻¹n 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₃.

The hypercube graph Q_n 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 2ⁿ 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.