# Graph Theory - Number of edges and vertices

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.

• It is a regular graph where the degree of each vertex is $k$. – Michal Adamaszek Mar 26 at 14:35
• No, I don't think so, it is not specified so. The only thing I can see is that every vertex has degree 2 – user654759 Mar 26 at 14:41
• 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. – Thomas Lesgourgues Mar 26 at 15:19
• Please choose another title ! – Peter Mar 26 at 17:42

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.