9
$\begingroup$

prove $n$-cube is a bipartite graph for all $n\ge1$

This is a problem in my textbook and I cannot figure it out at all and have a test on graph theory tomorrow any help would be appreciated since I am not very good with proofs

$\endgroup$
2
  • 3
    $\begingroup$ The vertices of the $n$-cube are the points $\{0,1\}^{n}$; two vertices are joined by an edge only if they differ in exactly coordinate, which means that the sums of their coordinates ($0 \le \sum_{i} x_i \le n$) differ by exactly $1$. Look at the parity of this sum. $\endgroup$
    – mjqxxxx
    Feb 12, 2013 at 21:07
  • $\begingroup$ See also math.stackexchange.com/a/227689/1543 $\endgroup$ Feb 13, 2013 at 12:04

5 Answers 5

12
$\begingroup$

When labeling your $n$-cube, you can assign the vertices strings of length $n$ from $(00..0)$ to $(11..1)$. For example a $2$-cube (or square) would be: $$00\ 01\\10\ 11$$ Now you can define two subesets of your graph $G= (X,Y)$. Where $X=${vertices who have an even number of $1$'s} and $Y=${vetices who have an odd number of $1$'s}.

By creating an edges {$1,0$} or {$0,1$} starting in $X$ and ending in $Y$ all edges are accounted for and therefore, the graph is bipartite.

$\endgroup$
4
$\begingroup$

Hint: If a graph is bipartite, it means that you can color the vertices such that every black vertex is connected to a white vertex and vice versa.

Hint: Consider parity of the sum of coordinates.

$\endgroup$
3
$\begingroup$

The vertices of the $n$-cube are vectors $(v_1,v_2,\ldots,v_n)$ with entries $v_i\in\{0,1\}$. Two vertices are adjacent if and only if their representing vectors differ in exactly one entry.

Now partition the vertex set into two subsets, consisting of all vertices whose representing vector has an even (resp. odd) number of $1$'s. This partition gives a bipartite graph.

$\endgroup$
0
$\begingroup$

Recall a graph ${ G }$ is bipartite if there is a partition ${ V(G) = X \sqcup Y }$ where each edge has one end in ${ X }$ and one end in ${ Y }$.

The ${ n-}$cube has vertex set ${ V(G) = (\mathbb{Z}/2\mathbb{Z}) ^n },$ with each vertex ${ v \in (\mathbb{Z}/2\mathbb{Z}) ^n }$ having neighbourhood ${ N(v) = \lbrace v + (1, 0, \ldots, 0), \ldots, v + (0, \ldots, 0, 1) \rbrace .}$

So letting ${ X = \lbrace v \in (\mathbb{Z}/2\mathbb{Z}) ^n : \sum _{1} ^{n} v _i = 0 \rbrace }$ and ${ Y = \lbrace v \in (\mathbb{Z}/2\mathbb{Z}) ^n : \sum _{1} ^{n} v _i = 1 \rbrace }$ gives a bipartition.

$\endgroup$
0
$\begingroup$

Alternately, here is "intuition by picture"

enter image description here

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .