Prove that Hypercube is Bipartite

In this article, we will show that every hypercube (Qn) is bipartite.

Bipartite: A Graph is Bipartite if we can divide the vertices of the graph into two sets such that no two vertices in the same set are adjacent to each other.

Hypercube: A Hypercube is denoted by Q_n. A hypercube has 2ⁿ vertices and each vertex has a degree equal to n.

The simplest way to construct a hypercube is to assign a distinct number from 0 to 2ⁿ – 1 to each vertex. Two vertices are connected only if they differ in exactly one-bit position ( the hamming distance between the vertices is 1 ).

Proof that Hypercube is Bipartite

The proof is based on the fact that vertices in a hypercube are connected only if the Hamming distance between them is exactly 1.

Suppose a vertex X. Assume the number of ‘1’ in X in binary is even. All the vertices adjacent to X differ exactly by one-bit position. It means the number of ‘1’ in the vertices adjacent to X is 1 more or 1 less than in X. Thus, we can say that the number of ‘1’ in the vertices adjacent to X must be odd.

For example, if X is 101 (even ‘1’), then it’s adjacent vertices are 111,001,100 (odd ‘1’).

Similarly, if we assume the number of ‘1’ in X to be odd. Then, the number of ‘1’ in the vertices adjacent to X must be even.

For example, if X is 001 (odd ‘1’) then it’s adjacent vertices are 101,011,000 (even ‘1’).

Thus, we can say that no two vertices with the same parity are adjacent to other each.

Therefore, we can split the vertices of the hypercube into 2 sets. The first set contains vertices with an odd number of ‘1’ and the second set contains vertices with an even number of ‘1’.

For example,

Split vertices of hypercube Q₃ in 2 sets.
Set 1: 100, 010, 111, 001 ( odd number of ‘1’ )
Set 2: 101, 000, 011, 110 ( even number of ‘1’ )

Basically, we have split the hypercube into two sets such that no edge connects the vertices belonging to the same set.

Therefore, we can say that the hypercube is bipartite.

References

Hamming Distance
Discrete Mathematics and Its Applications Seventh Edition Kenneth H. Rosen