Let $G'=(V',E')$ be a counterexample with $|V'|+|E'|$ minimum and let $\delta$ be the minimum degree of $G'$. Let $G_0$ and $G_1$ be the subgraphs of $G'$ induced by the vertices of $G'$ with first component $0$ and $1$ respectively.  Let $\delta_0$ and $\delta_1$ be the minimum degrees of $G_0$ and $G_1$ respectively.  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.