# If $G$ is a connected graph with $n$ vertices and $n - 1$ edges then $G$ is a tree, using Induction.

Prove the following Theorem. If $$G$$ is a connected graph with $$n$$ vertices and $$n - 1$$ edges, then $$G$$ is a tree.

I am still new to proof methods and not sure if this is the correct use of induction.

Base case: $$n = 1$$. Here, $$G$$ has $$0$$ edges and is a tree.

Assume every connected graph with $$k$$ vertices and $$k-1$$ edges is a tree.
Let $$G$$ be a connected graph with $$k+1$$ vertices that contains at least one cycle (no amount of edges are specified).

Let $$m$$ be the number of edges removed. Remove edges from each cycle to form a new graph $$G'$$.

$$G'$$ is a tree with $$k-1$$ edges and $$k+1$$ vertices. $$G$$ has $$k-1+m$$ edges.

If $$m=0$$ then $$G' = G$$ and $$G$$ is a tree.

• How do you know it's still connected after removing one edge from each cycle? – TokenToucan May 20 '15 at 17:30

Suppose we have a cycle-free, connected graph $G$ with $n$ vertices. and $n-1$ edges.

Because $G$ is cycle-free, there is a vertex with degree $1$. Delete this vertex.

We are left with a connected graph $G'$ with $n-1$ vertices and $n-2$ edges, which is a tree by induction. Reattaching the former pendant vertex does not introduce a cycle into the graph, as it had degree one, so the graph $G$ must be a tree.

**

This is the standard proof - I don't think it is possible to make your proof work. You do establish the inductive hypothesis, and work on a graph with $k+1$ vertices, which is good. However, your proof doesn't appeal to the inductive hypothesis later.

Additionally, it's not clear how you arrive at "G' is a tree with k-1 edges and k+1 vertices" (which is not a true statement). I think you're trying to translate the proof that trees are acyclic into a proof by induction.

• Why didn't you use a "n+1" when doing the induction proof? Isn't the "next step" always required for an induction proof? – onesevenfour May 20 '15 at 17:54
• I used $n$, and assumed that it was true for all numbers up to $(n-1)$. This is equivalent to using $(n+1)$ and assuming that it is true up to $n$. – TokenToucan May 20 '15 at 17:55