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.

Solution 1:

Your base case holds.

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.