Prove that we can turn a hypercube into a tree by deleting the correct number of edges

Question

An $n$-dimensional hypercube has $n2^{n-1}$ edges, and a tree has $n-1$ edges where $n= |V|$, so I know we need to delete the difference of these 2 quantities if we wanted to obtain a tree. However, I am asking how we could prove that we know that deleting this number of some edges would ever result in a connected graph, such that we could conclude that what we get is a tree. On some intuitive level, I have some justification for this, but I have been at a loss to come up with a formal proof of this. I have tried to systematize a way to remove cycles from the graph, but have been unsuccessful; any help would be appreciated.

Answer 1

Any connected graph, including an $n$-dimensional hypercube, has at least one spanning tree. As a (hopefully) more convincing argument than just citing a Wikipedia page, consider a graph $G$ and a connected subgraph $H$ which includes all vertices of $G$ and has the fewest possible number of edges. Then $H$ must be a tree because if not, we would be contradicting the assumption that $H$ has the fewest number of edges while still being connected.