Inductive proof that an n-cube is bipartite

941 Views Asked by At

For all $n\geq1$.

I am aware of the other proof where we assume sets with even number of 1's and odd number of 1's. I did an inductive proof and don't know if it is correct.

When $n=1$, it is trivial. When $n=2$, we have a square, which is a cycle of even length, so bipartite.

Can we say that for all $n\geq3$, the resulting n-cube is composed of squares and since we have established that squares are bipartite, the n-cube is also bipartite?

1

There are 1 best solutions below

8
On

Your argument would be partially correct but that wouldn't be an induction proof. However we can do one:

As you said, for $n = 1$, it is trivial. Now, suppose inductively it holds for $n$, i.e. $n$-cube is bipartite. Then, we can construct an $(n+1)$-cube as follows: Let $V(G_n) = \{v_1,...,v_{2^n}\}$ be the vertex set of $n$-cube. Since $(n+1)$-cube has $2^{n+1} = 2\cdot2^n$ vertices, copy $G_n$ and call it $G_n'$, and let $V(G_n') = \{v_1',...,v_{2^n}'\}$. Now, in order to construct $(n+1)$-cube, we should connect $v_i$ to $v_i'$ for all $1 \le i \le 2^n$.

Now by induction hypothesis, $G_n$ is bipartite. Let $A$ and $B$ be bipartition sets of $G_n$ and $A'$ and $B'$ be bipartition sets of the copy $G_n'$ (because by induction hypothesis, $G_n'$ is bipartite as well). Now notice that there is no edge from $A$ to $B'$ and similarly $A'$ to $B$. Therefore, we can partition vertex set of $G_{n+1}$ into two as $A \cup B'$ and $A' \cup B$ and we are done.