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.

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

Yes, the proof is correct. It can be written as follows:

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)$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.