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

^{n}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^{n} – 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 _{3} **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