My assignment is to prove that G = (V, E) is a tree if and only if |V | = |E| + 1 and G has no cycles.
However, I am having some trouble doing just that.
We defined a tree as a graph which is connected and doesn't have any cycles so the no cycles part of the proof is given,right? More specifically I can't figure out how to show that if a graph G = (V, E) has |V | = |E| + 1 and no cycles then it is connected.
Any tips, hints, etc. are welcome.
Thank you
Start with all edges removed. That would give you a graph with $|V|$ connected components. Now add the edges one by one. Each edge you add will reduce the number of connected components by $1$ (since it will connect two previously unconnected components). By the time you get to $|V| - 1$ edges, there is exactly one connected component.