Maximum number of edges that can be removed in a connected graph so that no vertex is left alone

Question

I have a connected graph G, defined by a list of lists where G[n] are all nodes that n connect to. I want to find out how many edges can be removed so that every vertex is connected to another vertex.

For example: G = [[1], [0, 2, 4], [1, 3], [2], [1, 3, 5, 6], [4], [4]]

We can remove 3 edges (1,2), (1,4) and (4,3)

I found a solution in that I can check every combination of edges and find the smallest one so that our criteria are met. I want to find a faster and more efficient way of doing this.

Answer 1

The algorithm to remove the maximum number of edges from an undirected graph that still leaves every vertex connected to another by an edge but can leave the resulting graph with vertices that cannot be reached from every other vertex would be

• LOOP E over edges
  • IF both of E's end vertices have degree > 1
    • REMOVE E from graph.