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$.
So this is how we tackle the problem: First, we put every vertex with an even degree sum in bipart $X$, and every vertex with an odd degree sum in bipart $Y$, which gives rise to a bipartition, as Leen proposed.

Then, given nod $V\_{x} = (0,b\_{2},b\_{3},\cdots ,b\_{k})$ form bipart $X$ and $V\_{y} = (1,b\_{2},b\_{3},\cdots ,b\_{k})$ from bipart $Y$ (where all $b\_{j}$'s are binary), we see that each pair of such vectors disagree on one single position in exactly $k$ ways; in other words each vertex $V\_{x}$ from $X$ is adjacent to exactly $k$ vertices $V\_{y}$ from $Y$ and vice versa, so that each vertex in the graph is of degree $k$, hence the graph is $k-regular$, as ml105 proposed.

Now what we have is a $bipartite$ $k-regular$ graph, for which the Marriage theorem guarantees the existence of a perfect matching.