# minimum number of edges that should be added to an undirected graph to make it a tree

Basically, it's this rosalind problem.

You're given a number of nodes and an adjacency list. My initial guess was that the answer was the number of connected components minus 1, since by joining every connected component you would have a connected graph, and since it's stated that there are no cycles, that would be a tree.

Why is this approach wrong? The real answer is just the number of nodes-1-number of edges, which I understand, but can't see how is this not equivalent to my answer.

Also, the sample dataset given bugs me. I see three connected components so I don't see why the answer is not 2. Bear in mind, i'm almost new to graph theory so i'm sorry if i'm missing something simple.

Clearly, if there are $$k$$ connected components you'll need exactly $$k-1$$ edges to connect them (without forming any cycle).
On the other hand, a tree with $$n$$ nodes must have exactly $$n-1$$ edges, so if the graph is acyclic and already has $$m$$ edges, then it is missing $$n-1-m$$ edges.
Regarding the example: the given graph has $$n=10$$ vertices, $$m=6$$ edges, and $$k=4$$ connected components (not 3), so the answer is $$3=k-1=n-m-1$$. The sets of vertices in each connected component are $$\{1,2,8\}, \{3\}, \{4, 6, 10\}$$, and $$\{5, 7, 9\}$$.
• Oh, i'm just stupid, thanks for the comment. I thought the sample dataset was wrong, since there was no $3$ in there, but you made me realize that lonely nodes don't appear in the adjacency list. Thanks Jan 14, 2021 at 21:15