# Induction: Every connected graph has a spanning tree

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?

• You should definitely use induction. Can you do the base case? If so, include it in your question. Then write down what the inductive step should be. – Alex G. Nov 19 '15 at 20:58
• I've editted my question, thanks. – YoTengoUnLCD Nov 19 '15 at 21:03

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.
• @YoTengoUnLCD Try proving that a connected graph with $n$ vertices and at least $n$ edges contains a cycle. Then, removing a cycle edge doesn't disconnect the graph... – Michael Biro Nov 19 '15 at 21:29
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$.