How to prove that a connected graph with $|V| -1= |E|$ is a tree?

Question

I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree.

Could somebody please provide an argument to establish this.

Answer 1

Suppose $|V| \ge 2$. Recall that the sum of the degrees of all vertices is $2|E|$. Since The graph is connected there cannot be a vertex of degree $0$.

Thus as $2|V|> 2|E|$ there is a vertex of degree one. Removing that vertex and the adjacent edge does not change that the graph is connected. And if the graph after removal is a tree, so is the graph itself.

Using this starting idea you can set up a proof by induction.

Answer 2

An empty graph on $n$ vertices has $n$ connected components, Suppose you have a graph and add an edge, then the number of connected components is reduced by at most one ( since this edge touches at most two connected components). Therefore a connected graph on $n$ vertices has at least $n-1$ edges).

Suppose a connected graph on $n$ vertices has $n-1$ edges, we must prove no cycle exists, suppose it does, if we remove an edge from the cycle we get a connected graph (because if we have a path that uses this edge, instead of using the edge we can go around the remaining part of the cycle). This is a contradiction, since the graph would have $n-2$ edges, and would hence not be connected.