0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (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. $\endgroup$ – bof Dec 11 '14 at 10:45
  • $\begingroup$ Yep, $k \geqslant 1 $. Edited.Please, no induction.I've never been good at going any further than building the induction hypothesis ! $\endgroup$ – Erfan Dec 11 '14 at 11:12
  • 3
    $\begingroup$ "Please, no induction. I've never been good at" Isn't that the best reason for practicing induction? $\endgroup$ – JiK Dec 11 '14 at 11:14
  • $\begingroup$ @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 !!!!! $\endgroup$ – Erfan Dec 11 '14 at 11:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Leen Droogendijk Dec 11 '14 at 13:39
2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A clearer hint please ? $\endgroup$ – Erfan Dec 11 '14 at 11:33
  • 1
    $\begingroup$ @elkoldo That wasn't a hint, he explicitly defined a matching. Um, what's your definition of the $k$-cube? $\endgroup$ – bof Dec 11 '14 at 11:43
  • $\begingroup$ Well I'm not clear on how to construct that perfect matching. I wrote the definition in the problem statement. $\endgroup$ – Erfan Dec 11 '14 at 11:47
  • $\begingroup$ 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? $\endgroup$ – Leen Droogendijk Dec 11 '14 at 13:37
  • $\begingroup$ Of course; Why is it a perfect matching? $\endgroup$ – Erfan Dec 11 '14 at 14:13
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.