Hypercube graph

Hypercube graph
The hypercube graph Q4
Vertices2n
Edges2n – 1n
Diametern
Girth4 if n ≥ 2
Automorphismsn! 2n
Chromatic number2
Spectrum
PropertiesSymmetric
Distance regular
Unit distance
Hamiltonian
Bipartite
NotationQn
Table of graphs and parameters

In graph theory, the hypercube graph Qn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

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.

Hypercube graphs should not be confused with cubic graphs, which are graphs that have exactly three edges touching each vertex. The only hypercube graph Qn that is a cubic graph is the cubical graph Q3.