Return to Answer

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_1)| \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.

Let $G'=(V',E')$ be a counterexample with $|V'|$ 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'$. Note that both $\delta_0$ and $\delta_1$ are at least $\delta-1$. By minimality, we have that $|V(G_0)| \geq 2^{\delta_0} \geq 2^{\delta-1}$ and that $|V(G_1)| \geq 2^{\delta_1} \geq 2^{\delta-1}$. Therefore, $|V(G')| \geq 2^{\delta}$, which contradicts that $G'$ is a counterexample.

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_1)| \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.

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_1)| \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.

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.

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_1)| \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.