Minimum Edge Cover of the Hypercube

discrete mathematicsgraph theoryinduction

I want to find the minimum edge cover of the n-dimensional hypercube $Q_n$. I think the answer is $2^{n-1}$ after doing some casework, but I am not entirely convinced: for $n=2,3,4$, the size of min edge cover is $2,4,8$ respectively. I also have an idea for the proof: because there is $n2^{n-1}$ edges in $Q_n$, and the degree of each vertex is $n$, as long as each of the vertices cover $n$ unique edges of $Q_n$( that is, the edges that each vertex cover is entirely different from the edges that other vertex covers) then the minimum edge cover is $2^{n-1}$. However, I can't figure out how to show it is possible to arrange the vertices such that they cover $n$ unique edges of $Q_n$. Some hint will be greatly appreciated!

Best Answer

Construction: You can construct a $Q_{n+1}$ by placing two $Q_n$ s side-by side, each with $2^n$ vertices and $n.2^{n-1}$ edges (since $\sum\limits_i degree(v_i)=2^n.n=2.e)$, and joining vertex $i$ from a $Q_n$ to the corresponding vertex $i^{\prime}$ for the other $Q_n$, with another $2^{n}$ edges, so that total number of edges in the resulting volume formed $=2.|E(Q_n)|+2^n=2.n.2^{n-1}+2^n=(n+1).2^n=|E(Q_{n+1})|$.

Now, completing the induction proof on the dimension $n$ of the hypercube:

Basis: for $n=2$, trivially select $2=2^{n-1}$ $||$ edges to cover 4 vertices and it's the minimum edge cover size.

Induction hypothesis: Let's assume till $n \leq m$, the minimum edge cover size be $2^{n-1}$

Induction Step: for $n=m+1$, construct $Q_{m+1}$ as described above by placing two $Q_m$s side by side and adding $2^{m}$ edges to connect the corresponding vertices.

  • Now, notice that in $Q_{m+1}$ there is exactly $2^{m+1}=2.2^m$ vertices obtained by combining two $Q_m$s and no extra vertex.
  • Also, by induction hypothesis, each of the $2^m$ vertices from the individual $Q_m$ s can be covered by selecting $2^{m-1}$ edges from the respective $Q_m$s.
  • Hence, if we combine those edges used to cover the individual $Q_m$s, we get $2.2^{m-1}=2^m$ edges, that cover all the $2^{m+1}$ vertices of $Q_{m+1}$, since there is no additional vertex.
  • Hence using $2^m=2^{(m+1)-1}$ edges we can cover the vertices in $Q_{m+1}$.
  • Also, notice that the edge cover size can't be less, otherwise we shall not be able to cover all the vertices of at least one of the component $Q_m$s, hence this is the minimum possible edge cover size.
  • It completes the proof that $2^{n-1}$ is the minimum edge cover size for a hypercube of dimension $n$, $\forall{n} \in N$.
Related Question