A spanning tree of a graph $G$ is a tree $T\subseteq G$, with $V_T=V_G$
Proof, by induction, that every connected graph $G$ with $n$ vertices contains a spanning tree.
Hint use as basis $|E|=n-1$.
I'm pretty lost, I've read the answers on a similar question here, but induction was not used for the proofs (and also, their definitions of a spanning tree was a bit different than mine).
As a (simple) graph on $n$ vertices with less than $n-1$ edges is disconnected, we take as a base $|E| = n-1$ then $G$ is a tree, so we're done.
The induction step would then be assuming this for some $k>n-1$ and proving it for $k+1$, right?
Could someone show me some more hints?