Given an undirected connected graph with N vertices and M edges, and a set S of K nodes of this graph.

Find the maximum number of edges that we can remove from the graph such that all these K nodes still remains connected (i.e there exist one component which has all these K nodes )

eg -: edges -:[[1 2], [1 3],[2 4],[3 4]] S = [1, 2, 4]

We can remove maximum of 3 edges [1, 3] and [3, 4] and [1, 4], removing any other edges makes given set of nodes disconnected.

How to solve this ?

I can only think of trying all 2^m subset of edges.