Induction: Every connected graph has a spanning tree

Question

Definition

A spanning tree of a graph $G$ is a tree $T\subseteq G$, with $V_T=V_G$

Question

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

Attempt

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?

Answer 1

Once you have proved your base case (for $k=n-1$), you assume the statement holds for some $k\ge n-1$. Then consider a connected graph with $k+1$ edges.

Can you remove an edge so that the remaining subgraph with $k$ edges is still connected? (Is that always the case? It better be...) If the subgraph with $k$ edges is connected, then it also has a spanning tree by the inductive hypothesis.

Answer 2

Proofs by induction (especially in graph theory) are often simpler to formulate and discover if one shows that a "minimal counterexample" cannot exist. This way, we do not even need to consider the number $n$ of vertices; we just consider a minimal (with respect to number of edges) counterexample $G$, i.e., $G$ is a connected graph that does not have a spanning tree and all graphs with less edges do have a spanning tree (this is the point that is actually the "induction in disguise"). Two cases can happen: Either $G$ is cycle-free or there is at least one cycle. In the first case, $G$ itself is a tree, contradicting the assumption that $G$ is a counterexample. In the second case, let $G'$ be the graph obtained from $G$ by removing one of the edges belonging to one of the cycles. Because that edge was in a cycle, $G'$ is still connected. A spanning tree for $G'$ would also be a spanning tree for $G$, hence there is none. But $G'$ has less edges than $G$, contradicting minimality of $G$.

Now if you are unhappy with the minimal-counterexample approach, it should be fairly easy to translate it into a "real" induction proof.