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.

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

If G = (V,E) is an acyclic graph and |E| = |V| + 1,
then G is a tree.

Lemma.  If G is a tree, then |E| = |V| + 1.
How could this be proved, preferably without induction?

Each component of G is a tree.
The sum of the number of vertices of the components = |V|.
The sum of the number of edges of the components = |E|.
By the lemma, |V| = |E| + number of components.
Thus there is but one component and G is a tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.