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!
Minimum Edge Cover of the Hypercube
discrete mathematicsgraph theoryinduction
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.