Degree and Bipartition Proofs for Hypercubes

Coordinates Determine the Neighbors

A hypercube is described by binary strings: its vertices record choices of 0 or 1 in each coordinate, and an edge represents changing exactly one choice. This description gives two useful structural facts. Each coordinate supplies one neighbor of every vertex, so the degree is the dimension. Also, changing one coordinate switches the parity of the number of 1s, so the vertices split into two parts with every edge crossing between them. We will prove both statements directly and check them on the first three positive-dimensional cubes.

For example, the vertices of \(Q_2\) are \(00,01,10,11\). The string \(00\) is adjacent to \(01\) and \(10\), because each differs from \(00\) in one coordinate; it is not adjacent to \(11\), which differs in two coordinates. The definition specifies both the vertices and adjacency rule, so it determines the whole graph without a drawing.

The Degree of Every Vertex

Proof. Fix a vertex \(x=x_1x_2\cdots x_n\) of \(Q_n\). For each coordinate \(i\) with \(1\leq i\leq n\), let \(x^{(i)}\) be the string obtained by replacing \(x_i\) by the other binary value and leaving every other coordinate unchanged. Then \(x^{(i)}\) differs from \(x\) in exactly one coordinate, so \(x^{(i)}\) is adjacent to \(x\). If \(i\neq j\), the strings \(x^{(i)}\) and \(x^{(j)}\) differ at coordinate \(i\), so they are distinct. Conversely, any neighbor of \(x\) differs from it in exactly one coordinate \(i\), and therefore equals \(x^{(i)}\). There are exactly \(n\) such neighbors. When \(n=0\), there are no coordinates and no neighbors, so the degree is \(0=n\) as well. \(\square\)

The proof is a complete description of the neighborhood: changing coordinate \(i\) gives one neighbor, and every neighbor arises from one such change. The distinctness matters. If two coordinate changes produced the same neighbor, counting coordinates would overstate the degree; the proof rules that out.

Parity Gives a Bipartition

The weight of a binary string is the number of its coordinates equal to 1. The parity of its weight is even or odd according to whether that number is even or odd. Define \(X\) to be the set of even-weight strings and \(Y\) the set of odd-weight strings.

Proof. Every binary string has either even weight or odd weight, but not both, so \(X\) and \(Y\) are disjoint and together contain every vertex. Consider any edge \(xy\). By the definition of \(Q_n\), its endpoints differ in exactly one coordinate. If that coordinate changes from 0 to 1, the weight increases by 1; if it changes from 1 to 0, the weight decreases by 1. In either case, the weight changes by an odd number, so its parity switches. Thus one endpoint has even weight and the other has odd weight. Every edge therefore crosses between \(X\) and \(Y\), as required. For \(Q_0\), the sole string has weight 0, so \(X\) contains that vertex and \(Y\) is empty; there are no edges that could violate the condition. \(\square\)

A bipartition is allowed to have an empty part. This point handles \(Q_0\): it has one vertex but no edges, and the condition that every edge crosses the parts is satisfied because there are no edges.

Proof. Suppose \(n\geq 1\). Map each string to the string obtained by changing its first coordinate and leaving its other coordinates fixed. Applying this map twice returns the original string, so it is a bijection. Changing one coordinate switches parity, so this bijection pairs every even-weight string with exactly one odd-weight string. Hence \(|X|=|Y|\). There are \(2^n\) binary strings, since each of the \(n\) coordinates has two independent choices. Therefore \(|X|+|Y|=2^n\), and equality of the two sizes gives \(|X|=|Y|=2^{n-1}\). When \(n=0\), the only string is empty and has weight 0, giving the stated sizes. \(\square\)

Worked Checks on Small Cubes

A General Edge Count and a Common Mistake

The proofs also give a useful count. For \(n\geq 1\), fix a coordinate \(i\). Each assignment of values to the other \(n-1\) coordinates determines exactly one edge that changes coordinate \(i\): its two endpoints have those fixed values and have 0 and 1, respectively, in coordinate \(i\). There are \(2^{n-1}\) assignments, so there are \(2^{n-1}\) edges changing coordinate \(i\). Edges changing different coordinates are distinct, because an edge in \(Q_n\) differs in exactly one coordinate. Every edge changes one coordinate. Consequently, the total number of edges is \(n2^{n-1}\). This count is obtained directly from the definition; it agrees with counting the \(n\) incident edges at each of the \(2^n\) vertices and dividing by two, since each edge has two endpoints.

Common mistake: confusing dimension and number of vertices. A tempting but incorrect calculation is to say that \(Q_3\) has eight vertices, so every vertex has degree \(8\). This counts all vertices, including the vertex itself and those not adjacent to the chosen vertex. For \(000\), the only neighbors are \(001,010,100\), so its degree is \(3\), not \(8\). In general, the number of vertices is \(2^n\), while the number of neighbors of a fixed vertex is \(n\), one for each coordinate. In \(Q_3\), the direct edge count is \(3\cdot 2^{3-1}=3\cdot4=12\), not the count that would result from assigning degree 8 to every vertex.

These facts are useful whenever the hypercube is used as a model of states connected by one-bit changes. The degree tells how many single-coordinate moves are available from every state. The parity partition gives a simple structural guarantee: every allowed move goes between opposite parity classes. The proofs depend only on the binary-string definition, so they apply in every dimension, including the zero-dimensional boundary case.