For an undirected graph with 30 vertices and 4 connected components, the minimum number of edges is 26.

How to think about it

For any undirected graph:

  • Each connected component with nin_ini​ vertices needs at least ni−1n_i-1ni​−1 edges to be connected (a tree on nin_ini​ vertices).
  • If the graph has kkk connected components, and the total number of vertices is nnn, then the minimum total number of edges happens when each component is a tree.

Let the components have sizes n1,n2,n3,n4n_1,n_2,n_3,n_4n1​,n2​,n3​,n4​ with:

n1+n2+n3+n4=30n_1+n_2+n_3+n_4=30n1​+n2​+n3​+n4​=30

Then the minimum number of edges is:

∑i=14(ni−1)=(∑i=14ni)−4=30−4=26\sum_{i=1}^{4}(n_i-1)=\left(\sum_{i=1}^{4}n_i\right)-4=30-4=26i=1∑4​(ni​−1)=(i=1∑4​ni​)−4=30−4=26

So regardless of how the 30 vertices are split into 4 nonempty connected components, the smallest possible number of edges is always:

26\boxed{26}26​