2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Alex G. Nov 19 '15 at 20:58
  • $\begingroup$ I've editted my question, thanks. $\endgroup$ – YoTengoUnLCD Nov 19 '15 at 21:03
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! I tried to do this, but I couldn't prove that there was an edge I could remove and keep the graph connected. $\endgroup$ – YoTengoUnLCD Nov 19 '15 at 21:28
  • 2
    $\begingroup$ @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... $\endgroup$ – Michael Biro Nov 19 '15 at 21:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.