Every connected graph with v vertices and v-1 edges is a tree

Question

I am supposed to prove that any graph that is connected and has v vertices and v-1 edges is a tree. I know this is a basic fact about trees, but i'm not sure why exactly it is.

Answer 1

Let $V$ be set of vertices with $\#V\ge 2$. Then a minimal connected graph on $V$ is a connected graph in which if any edge is removed then the graph is no more connected.

Any minimal connected graph is a tree

Since the graph is connected it's sufficient to prove it is acyclic. Suppose there is a cycle $v_0\to v_1 \to \cdots \to v_n \to v_0$. Remove the edge $v_n \to v_0$, then any path that included the edge $v_n \to v_0$ can be reconstructed by replacing $v_n\to v_0$ by $v_n\to v_{n-1}\to \cdots \to v_0$, so the graph is still connected but with less edges - contradiction to minimality, so no cycles exist. Hence minimal connected graphs are trees.

Any connected graph contains a minimal connected subgraph (with same number of vertices)

Indeed, we can just remove edges one by one untill we cannot remove more without violating connectedness. Resulting subgraph of original graph is minimally connected.

Hence, any connected graph contains a tree as a subgraph. (Same number of vertices)

Follows immediately.

Then you could prove the following:

If a tree $T$ has $n$ vertices, then number of edges $e(T)=n-1$.

Use induction on $n$ - consider you have a tree with $n$ vertices. Remove a leaf from the graph, and resulting graph is a tree with $n-1$ vertices, so you can do induction.

Finally, since your graph is connected and has $n$ vertices and $n-1$ edges, it contains a tree as a subgraph with $n$ vertices, which has $n-1$ edges. But your graph already has $n-1$ edges, and so your graph is minimally connected, so is a tree.