# Qn is bipartite

Hi i'd like to know if this proves that $Q_n$ is bipartite or I should write it different, THANKS!!

Let $G$ be a $Q_n$ graph.

In $Q_n$ vertices are represented by vectors ($v_1$,$v_2$,....$v_n$) where ∀ $v_i\in \{1,0\}$

In $Q_n$ two vertex are connected if its representatives vectors differ in one entry.

We can define two subsets in $G$:

$X$ = { vertex with even entries of $v_i$= 1 }

$Y$ = { vertex with odd entries of $v_i$= 1 }

If $u$ in $V($G$)$ and $v$ in $V($G$)$ and exists ($u$, $v$ ) in $E($G$)$ then {$u$ in $X$ and $v$ in $Y$} or {$v$ in $X$ and $u$ in $Y$} since the differ in one entry one of the vertex has even entries of $v_i$= 1 equivalent to 2$k$ and the other one should has 2$k$+1 entries $v_i$= 1 or 2$k$-1 entries $v_i$= 1 .

So $X$ and $Y$ are a partition in $G$, the $Q_n$ is bipartite.

• It could be written a little better, but yes, it’s correct. – Brian M. Scott Sep 10 '16 at 20:15

Define the weight of a vertex $v=v_1 v_2 \cdots v_n$ of $Q_n$ to be the number of $v_i$'s that are equal to $1$. Let $X$ be the set of vertices of $Q_n$ of even weight, and let $Y$ be the set of vertices of $Q_n$ of odd weight. Observe that if $uv$ is an edge of $Q_n$ joining vertices $u$ and $v$, then the weights of $u$ and $v$ differ by $1$, whence their weights have different parity. It follows that every edge of $Q_n$ joins a vertex in $X$ to a vertex in $Y$. Hence, $Q_n$ is bipartite with bipartition $(X,Y)$.