I’ve encountered a problem in one of my projects, that can be boiled down to a graph formulation, and although I’ve successfully applied plenty of graph algorithms in my working life, I struggle with finding the right approach here. Here is the boiled down problem formulation:

My graph consists of a number of sets of nodes. Per definition, edges can only exist between sets and not between nodes within a set. For a graph to be valid, any sub-graph can at most contain one node from each set. Given an invalid graph, how can I remove edges to make it valid, while maximizing connectivity within the resulting sub-graphs?