Relation between vertices and edges in a tree?

Question

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?

Answer 1

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?

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:

So far I am also getting trees which have more than n-1 edges along with n-1 edges trees

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.

Answer 2

A tree is either defined as the graph with the minimum number of edges to be connected or as the maximum number of edges to have no circle. Both these numberes are $n-1$. So if you have a "tree" with more edges it has a circle and at least one edge can be removed, while still keeping a connected graph.

If you have n verticies it is possible to start with one vertex connected it to one of the unconnected vertices. Now take the connected part and add one edge to connected one of the unconnected vertices until every vertex is connected. This way you will get a tree and will have excactly n-1 edges (One for each vertex added to the starting vertex).