I have an undirected graph with weights on each edge. I want to remove a set of edges such that each vertex has degree at most K, but I want to keep the maximum possible weighted sum of edges.

Example: 1-2 with weight 3

1-3 with weight 3

1-4 with weight 3

1-5 with weight 4

5-6 with weight 3

5-7 with weight 3

5-8 with weight 3

and K = 3

Output: we can remove edge between 1 and 5 and get maximum sum as 18

Question: Can it be solved in polynomial time complexity ? If yes, please help me understand the algorithm for the same.

Thanks