# Prove that a cycle free graph with |E| = |V|-1 is a tree

I have to prove that a cycle free graph |E| = |V|-1 is a tree, (|E|= #edges, |V| = #vertices). I used induction for it.
Base case: Let G=(V,E) be a cycle free graph with |E|=n and |V|=n+1. For n = 1 we get a graph with 1 edge and two vertices so the graph is cycle free and connected => by def a tree.
IH: Let the statement be true for all graphs G=(V,E) |E|<= n, |V|<= n+1
IS: Let G=(V,E) be a cycle free graph with |E|= n+1 and |V|=n+2. Since G is cycle free and |E|<|V| there must be a vertex v with degree 1. Vertex v has just one incident edge e, build a graph G' with G without v and e. So G' has |E|=n and |V|=n+1 because of IH G' must be cycle free and connected so G' is a tree, if you take G' and put v and e in it to build G again, you would still have a tree because you couldnt create a cycle and it still would be connected so G must be also a tree.
Would this proof by induction be correct?

I also thought of a proof by contradiction.
Suppose G=(V,E) is not a tree, then G has to have more than one component because G is cycle free and |E| = |V|-1 applies. Because of those properties G cant have more than one component and must be connected => a tree. Im not sure if the last part is enought.

• any feedback would be great! – Jag Jan 28 '20 at 15:48
• Terribly written proof which I doubt. – William Elliot Feb 2 '20 at 0:46