# Perfect matching in k-cubes

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.

• (1) Why $k\ge2$, the $1$-cube also has a perfect matching. (2) The $k$-cube is a regular bipartite graph, so you could use the bipartite matching algorithm which is simpler than Tutte's theorem. (3) You can prove by induction on $k$ that the $k$-cube has a perfect matching. (4) You can prove by induction that (for $k\ge2$) the $k$-cube is Hamiltonian; of course a Hamiltonian graph with an even number of vertices has a perfect matching. (5) See the answer by Leen Droogendijk. – bof Dec 11 '14 at 10:45
• Yep, $k \geqslant 1$. Edited.Please, no induction.I've never been good at going any further than building the induction hypothesis ! – Erfan Dec 11 '14 at 11:12
• "Please, no induction. I've never been good at" Isn't that the best reason for practicing induction? – JiK Dec 11 '14 at 11:14
• @bof Hey hold on a sec there, are you sure that the "k-cube" is equivalent to "regular bipartite graph" ? 'cuase if that's the case, the marriage theorem is all we need !!!!! – Erfan Dec 11 '14 at 11:20
• In one partite set you put the numbers whose digits have an even sum, in the other you put the numbers whose digits have an odd sum. No induction required. – Leen Droogendijk Dec 11 '14 at 13:39

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.

• A clearer hint please ? – Erfan Dec 11 '14 at 11:33
• @elkoldo That wasn't a hint, he explicitly defined a matching. Um, what's your definition of the $k$-cube? – bof Dec 11 '14 at 11:43
• Well I'm not clear on how to construct that perfect matching. I wrote the definition in the problem statement. – Erfan Dec 11 '14 at 11:47
• I already have constructed the perfect matching for you. My 'binary vector of length $k$' is the same as your '$k$-tuple consisting of 0 and 1'. The two vertices I use for each edge of the matching only differ in one position. Can you be clearer about what you don't understand? – Leen Droogendijk Dec 11 '14 at 13:37
• Of course; Why is it a perfect matching? – Erfan Dec 11 '14 at 14:13

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.

For k cube graph, we have 2^k number of the vertex that is even number of vertex. now arrange all the vertex in a circle and number them according to grey code. so we will have a cycle of an even number of vertices with some interconnections in-between. and we know that we have perfect matching for a cycle with an even number of vertices, hence proved.