Given positive integer k, let H be the subgraph of Q_{2k+1} (a 2k+1 cube) induced by the vertices in which the number of ones and zeros differs by 1. Prove that H is regular and compute the order and size of H.
Honestly don't really know where to begin here. If someone could guide me in the right direction I would really appreciate it.
To ease up notation let's put $n = 2k + 1$, and remember that $n$ is odd.
The vertices of $Q_n$ are all the $2^n$ strings of zeroes and ones.
Two types of such vertices go in $H$ : those that have $\lfloor \frac{n}{2} \rfloor$ zeroes and $\lceil \frac{n}{2} \rceil$ ones, or vice-versa. Focus on the former. In how many ways can you have $\lfloor \frac{n}{2} \rfloor$ zeroes in $n$ positions ? It's the same for strings with more zeroes than ones, so double that and you get the order of $H$.
Now take some vertex $v \in V(H)$, and suppose wlog that $v$ has $\lfloor \frac{n}{2} \rfloor$ zeroes and $\lceil \frac{n}{2} \rceil$ ones. In $Q_n$, the $n$ neighbors of $v$ are those that differ by exactly one digit. When we restrict this condition to the vertices of $H$, the only way to find such a neighbor is to switch a one of $v$ for a zero (Why ?). The number of such digits you can flip gives you the degree of $v$.