Minimum number of edges that have to be removed in a graph to make it acyclic

Question

Given an undirected graph with n nodes and k edges , find the minimum number of edges that have to be removed in order to attain an acyclic graph. I initially thought that the minimum number of edges that need to be removed is the number of cycles that exist in the graph since each cycle needs one edge to be removed.

Answer 1

Basically, we combine these observations:

• An acyclic graph is another name for a forest, a union of disjoint trees.
• If a tree has $n \geq 1$ vertices, then it has $n-1$ edges.
• Each connected component has a spanning tree.

If the connected components in the original graph have $c_1,c_2,\ldots,c_k$ vertices, then the any union of spanning trees for each component has exactly $$(c_1-1)+(c_2-1)+\cdots+(c_k-1) = (c_1+\cdots+c_k)-k$$ edges. The number of edges we need to delete is thus $$|E(G)|-(c_1+\cdots+c_k)+k.$$