A hypercube has \(2^m\) vertices for some \(m \in \mathbb{N}\). The Hamming encoding of the vertices of a hypercube assigns to each vertex a unique binary string of length \(m\) (\emph{e.g.} for a standard square with \(4\) vertices the Hamming encoding will be \(\{ 00, 01, 10, 11 \}\)). The Hamming encoding is such that every pair of vertices connected by an edge in the hypercube differ by exactly one bit in their Hamming encoding

If \(x\) is a vertex in a hypercube, denote \(h(x)\) as the Hamming encoding of \(x\) and \(h(x)_{j}\) as the \(j^{th}\) bit of the Hamming encoding. The Hamming distance of two vertices \(x\) and \(y\) is the number of bits that differ between \(h(x)\) and \(h(y)\)(\emph{i.e.} \(d(00,01) = 1\) and \(d(00,11) = 2\)). This is equivalent to the distance assigned by the standard graph metric and implies that the diameter of the hypercube is the number of bits in the Hamming encoding.