Question: Are there any good video lectures available on Analytic Number Theory? I have a decent background of complex analysis but I have just started Analytic Number Theory.

Answer: 
A Matching $\mathcal{M}(V^{\prime}, E^{\prime})$ is a subgraph of $G$ such that for any two $e\_{1}, e\_{2} \in E^{\prime}$, $e\_{1} \cap e\_{2} = \emptyset$. That is, no two edges in the matching share a common vertex. A Perfect Matching uses all the vertices of $G$.

Remember that hypercubes are constructed as follows. Given $Q\_{n}$, we create a second copy of $Q\_{n}$. To the first copy, we append a $0$ to the strings for each vertex. To the second copy, we append a $1$ instead.

Consider $Q\_{1}$, a single edge. This is trivially a perfect matching. Now consider $Q\_{2}$, which is constructed from two instances of $Q\_{1}$:

```
00 - 01
|    |
10 - 11

```

Think of the left edge as the first $Q\_{1}$ and the right edge as the second $Q\_{1}$. If we remove the top and bottom edges of $Q\_{2}$, we are left with two disjoint copies of $Q\_{1}$ and a perfect matching.

Now apply this reasoning inductively. Though I think Leen Droogendijk's construction is a much cleaner way than induction. He and I are really saying the same thing, and you can apply either proof technique.

> 
> 
> > 
> > @Leen That shows that the k-cube is bipartite. But how can we show it's also k-regular ?
> > 
> > 
> > 
> 
> 
> 

Each vertex is a binary string, and is adjacent to vertices where the two strings differ in exactly one place. We can vary exactly one character in $n$ ways. So each vertex in $Q\_{n}$ has degree $n$.
Use the representation of the $k$-cube as a binary vector of length $k$.
For each set of binary digits $b2,\ldots,b\_k$ you have an edge between
$(0,b\_2,\ldots,b\_k)$ and $(1,b\_2,\ldots,b\_k)$.

Now show that this constitutes a perfect matching.