Perfect matching in k-cubes

Question

I want to show that every k-cube has a perfect matching for $ k \geqslant 1 $. (A k-cube is a graph whose vertices are labeled by k-tuples consisting of $ 0 $ and $1$ , and each two adjacent vertices are different in only one digit.)

According to Tutte's theorem, our graph has a perfect matching $\iff$ $$o(G-S) \leqslant \vert S \vert $$ for all $$S\subset V$$ where $o$ denotes the number of components with odd number of vertices, but the problem is that for arbitrary k the only way is to check all possible subsets $ S $ which is impractical and irrational. I don't think Tutte's theorem is efficient here.

Answer 1

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$.

Answer 2

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.

Answer 3

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.