Let $G'=(V',E')$ be a counterexample with $|V'|+|E'|$ minimum and then with the dimension of the hypercube in which $G'$ lives minimum.  Let $G_0$ and $G_1$ be the subgraphs of $G'$ induced by the vertices of $G'$ with first component $0$ and $1$ respectively.  Note that neither $G_0$ nor $G_1$ is empty, else $G'$ sits in a hypercube of lower dimension.  

Now let $\delta_0$ and $\delta_1$ be the minimum degrees of $G_0$ and $G_1$ respectively, and  let $\delta$ be the minimum degree of $G'$.   If $\delta_0 < \delta_1$, then deleting any edge of $G_1$ does not change the minimum degree of $G'$.  Thus, by choice of $G'$, we have $\delta_0=\delta_1$.  By minimality, we have that $|V(G_0)| \geq 2^{\delta_0}$ and that $|V(G_0)| \geq 2^{\delta_1}$.  Therefore, $|V(G')| \geq 2^{\delta_0+1}$.  But $\delta \leq \delta_0+1$, which contradicts that $G'$ is a counterexample.