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.

bipartite

Hypercube: A Hypercube is denoted by Qn. A hypercube has 2n 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 2n – 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 ).

hypercube

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 same parity are connected in a hypercube.

Therefore, we can split the vertices of a 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 Q3 in 2 sets.
Set 1: 100, 010, 111, 001 ( odd number of ‘1’ )
Set 2: 101, 000, 011, 110 ( even number of ‘1’ )

every hypercube is bipartite

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

Leave a Comment

Your email address will not be published. Required fields are marked *