I know the following relation between vertices and edges of a tree –
Any connected graph(undirected) with n vertices and $n-1$ edges is a tree.
My question is suppose I have an undirected connected graph with n vertices. Then is it possible that I can have more or less than $n-1$ edges and still get a tree?
I tried making all possible trees with $4$ vertices. So far I am also getting trees which have more than $n-1$ edges along with n-1 edges trees. So I suppose we can have more than $n-1$ edges. But this is just a hit and trial thing. Is this true for any finite number of vertices?
Best Answer
Of course you can have more than $n-1$ edges. The graph won't be a tree, but in general, you can have at most ${n\choose 2}$ edges in a graph with $n$ vertices. For example, a full graph on $3$ vertices has $\frac{3\cdot2}{2}=3$ edges, which is more than $n-1=2$.
You cannot have a connected graph with less than $n-1$ edges, however.
Also, you claim:
This is simply false. You are getting graphs with more than $n-1$ edges, but they are most certainly not trees. There is a theorem that proves that.