Hypercube graph

Hypercube graph
The hypercube graph ${\displaystyle Q_{4}}$
Vertices	${\displaystyle 2^{n}}$
Edges	${\displaystyle 2^{n-1}n}$
Diameter	${\displaystyle n}$
Girth	4 if ${\displaystyle n\geq 2}$
Automorphisms	${\displaystyle n!2^{n}}$
Chromatic number	2
Spectrum	${\displaystyle \{(n-2k)^{\binom {n}{k}};k=0,\ldots ,n\}}$
Properties	Symmetric Distance regular Unit distance Hamiltonian Bipartite Polytopal
Notation	${\displaystyle Q_{n}}$
Table of graphs and parameters

In graph theory, the hypercube graph ${\displaystyle Q_{n}}$ is the edge graph of the ${\displaystyle n}$-dimensional hypercube, that is, it is the graph formed from the vertices and edges of the hypercube. For instance, the cube graph ${\displaystyle Q_{3}}$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. ${\displaystyle Q_{n}}$ has ${\displaystyle 2^{n}}$ vertices, ${\displaystyle 2^{n-1}n}$ edges, and is a regular graph with ${\displaystyle n}$ edges touching each vertex.

The hypercube graph ${\displaystyle Q_{n}}$ may also be constructed by creating a vertex for each subset of an ${\displaystyle n}$-element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each ${\displaystyle n}$-digit binary number, with two vertices adjacent when their binary representations differ in a single digit. It is the ${\displaystyle n}$-fold Cartesian product of the two-vertex complete graph, and may be decomposed into two copies of ${\displaystyle 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 ${\displaystyle Q_{n}}$ that is a cubic graph is the cubical graph ${\displaystyle Q_{3}}$.