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.