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.
$\endgroup$ 11 Answer
$\begingroup$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)$.
$\endgroup$ 1
