-14
$\begingroup$

Let $Q_k$ be the graph where the vertices are the $k$-tuples with 0 or 1 in the entries, and two vertices are adjacent if and only if they differ by one entry. For example, $Q_2$ is the graph with $$V(Q_2) = \{(0,0),(0,1),(1,0),(1,1)\}$$ and $$E(Q_2) = \{(0,0)(0,1),(0,0)(1,0),(0,1)(1,1),(1,0)(1,1)\}.$$

How many vertices and edges does $Q_k$ have?

So, I have found that vertices are $2^k$. However, what is the number of edges? Is it also $2^k$?

And also, show that the graph $Q_k$ is bipartite. I don't know where to start.

$\endgroup$
  • $\begingroup$ It is a regular graph where the degree of each vertex is $k$. $\endgroup$ – Michal Adamaszek Mar 26 at 14:35
  • $\begingroup$ No, I don't think so, it is not specified so. The only thing I can see is that every vertex has degree 2 $\endgroup$ – user654759 Mar 26 at 14:41
  • 1
    $\begingroup$ No, it's a fact, you are defining the k cube. Each vertex will be connected to k other vertices, one for each coordinate of its k-tuple. Therefore it is k regular, and you can deduce the number of edges. $\endgroup$ – Thomas Lesgourgues Mar 26 at 15:19
  • 3
    $\begingroup$ Please choose another title ! $\endgroup$ – Peter Mar 26 at 17:42
1
$\begingroup$

Let $Q_k$ be the graph where the vertices are the k-tuples of $0$ or $1$ in the entries, and two vertices are adjacent if and only if they differ by one entry.

Let $v=(a_1,\ldots,a_k)$ be one vertex of $Q_k$, then $v$ is connected to $k$ other vertices : the vertices with exactly one difference is their $k$-tuple. Therefore $Q_k$ is $k$-regular. Then $$ \vert V(Q_k)\vert = \frac{k\vert E(Q_k)\vert}{2}=k2^{k-1}$$

Now Let $A$ be the set of $k$-tuples with an even number of 0, and $B$ be the set of $k$-tuples with an odd number of 0. Then for any two vertices $v_1,v_2\in A$ (resp. $B$), if $v_1\neq v_2$ then they must differ by an even number of coordinates, and hence cannot be connected. Each set is a stable set (no two vertices insides are joined), therefore $Q_k$ is bipartite.

$\endgroup$

Your Answer

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