$\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 Answers

$\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$ $\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$ $\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$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy