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.

Answer 2

A set of edges in a graph where every node touches at least one edge is called an edge cover of the graph. Your problem is equivalent to finding the smallest edge cover of the original graph; once you have it, deleting all the other edges will give you your answer.

The good news is that the problem of finding the smallest edge cover in a graph is solvable in polynomial time. The basic idea is to first find a maximum matching in the graph (a set of edges where no two edges share an endpoint) and then adding in additional edges to cover the remaining uncovered nodes. Polynomial time algorithms for finding maximum matchings of graphs have been known about since the 1960s but aren’t trivial to code up, so your best bet might be to find an existing software package that provides access to such an algorithm.