Given an undirected graph, We need to convert it into a connected graph by adding/removing the edges keeping the summation of absolute difference of change in degree of nodes minimum. There can be multiple edges. Formally, we need to minimize: $ $ \sum_{i = 1}^{i = n} |d_i – e_i|$ $ Where, $ e_i$ is the new degree of node i.

My approach was separating all the connected components first and then for every connected component, I noted down the edges which were not present in the DFS tree. These edges do not contribute to the connectivity of the graph and hence I can redirect them to other components to connect them. Is this claim correct? Also since the number of these type of edges can be arbitrary, what would be the constraints under which I use them to connect to other components.

The algorithm should work in linear time.