Largest number of edges removed from $Q_{10}$ such that the graph always has a Hamiltonian cycle. What is the largest number of edges that can be removed from $Q_{10}$ such that the graph always has a Hamiltonian cycle.
Obviously it is $\leq 8$ as otherwise you can take $9$ edges away from one vertex and no cycle is possible.
$Q_n$ is the hyper-cube graph. 
Also I have worked out that for $Q_3$ the answer is 1.
Thanks so much.
 A: Recall that $Q_n$ can be constructed with a vertex set consisting of all binary sequences of length $n$, where two sequences are adjacent if they differ in exactly one entry. 

Lemma. Every edge $e$ of $Q_n$ is contained in exactly $n-1$ squares (induced $4$-cycles). Moreover, $e$ is the only common edge in any two of these squares.

Proof: Let $(v_0,v_1)$ be an edge differing in the $ith$ entry. Now $v_0$ is adjacent to exactly $n-1$ other vertices. But if $v_2$ is any one of these, say differing from $v_0$ in the $j$th entry, with $i\neq j$, then there is a unique vertex $v_3$ that differs from $v_2$ in the $i$th entry and differs from $v_1$ in the $j$th entry and of course $\{v_0,v_1,v_2,v_3\}$ induces a $4$-cycle. The moreover part follows from the uniqueness of $v_3$.
We now  prove the following, which is actually stronger than what you require.  

Theorem. For any $n\geq 2$, let $H$ be a subgraph obtained from $Q_n$ by deleting $n-2$ edges. Then every edge of $H$ is contained in a Hamiltonian cycle.

We proceed by induction, with the base case being trivial. So suppose we delete $n-2$ edges from $Q_n$. Let $H$ be the resulting subgraph. 
Let $e=(v_0,v_1)$ be an edge in $H$ where $v_0$ and $v_1$ differ in the $i$th entry. We may assume without loss of generality that the $i$th entry of $v_0$ is $0$. Since we have only deleted $n-2$ edges, we can conclude that $e$ is contained in a square in $H$, say $\{v_0,v_1,v_2,v_3\}$.
Now, let $Q_{n-1}^0$ be the subgraph of $Q_n$ induced by those vertices whose $i$th entry is $0$, and let $Q_{n-1}^1$ be the subgraph of $Q_n$ induced by those vertices whose $i$th entry is $1$. Of course both of these subgraphs are isomorphic to $Q_{n-1}$. Let $H_0$ and $H_1$ be the corresponding induced subgraphs of $H$. Note that the edge $(v_0,v_2)$ is in $H_0$ and $(v_1,v_3)$ is in $H_1$.
Now, if, in forming $H$, not all of the $n-2$ edges that were deleted were in either $Q_{n-1}^0$ or $Q_{n-1}^1$, then at most $n-3$ edges were deleted from $Q_{n-1}^0$ and $Q_{n-1}^1$ respectively. Apply induction to obtain a Hamilton cycle $C_0$ in $H_0$ containing the edge $(v_0,v_2)$ and a Hamilton cycle $C_1$ in $H_1$ containing the edge $(v_1,v_3)$. Deleting these two edges and adding in $(v_0,v_1)$ and $(v_2,v_3)$ gives a Hamiltonian cycle of $H$ containing our arbitrarily chosen edge $e$. This argument in a picture:

Now, suppose that all $n-2$ edges that were deleted were in, say, $Q_{n-1}^0$. If we reinstate one of these, then there is a Hamiltonian cycle $C_0$ containing $(v_0,v_2)$. Thus in $H_0$ there is a Hamilton path from a vertex $w$ to a vertex $x$ containing $(v_0,v_2)$.  Since $H_1=Q_{n-1}^1$, the Hamilton cycle that "mirrors" $C_0$ (say $C_1$) is in $H_1$. Also, all edges between $Q_{n-1}^0$ and $Q_{n-1}^1$ in $Q_n$ are in $H$. Let this set of edges be $B$.  
The subgraph of $H$ consisting of just the edges in $B,C_1$ and $C_0\setminus (w,x)$ can be drawn (relabelling $w$ and $x$ if necessary) as the obvious generalization of the following picture for $n=4$:

It is easy to check that this subgraph has a Hamiltonian cycle containing $e$, obtained by alternating edges between $B$ and $C_1\cup C_0\setminus (w,x)$. For example:

