G is an undirected connected graph with positive costs on all edges. Given is edge e whose cost is strictly more than 10. We need to answer whether the MST cost will improve if the cost of e is reduced by 10.
I know of a solution that involves generating a new graph with only edges with cost<cost(e)-10. What's wrong with this much simpler solution:
Take one of e's vertices v. Find the minimal cost edge incident to v. Now reduce e's cost and find the minimal cost edge incident to v again. If there was a change, it means that prim would find a better MST and the cost is improved. If not, it means that prim would find the same MST and the cost stays the same.
What's wrong with this logic?
related to Update minimum spanning tree with modification of edge
I don't think that your solution is correct.
Consider the following graph G = (V, E), V = {a, b, c, d, e}, E = {ab, bc, cd, de, ae, bd} and the respective weights are {5, 10, 10, 5, 17}.
By running Kruskal or Prim, we find that our MST is {ab, bc, cd, de}, and his weight is 30.
Now, let's reduce the weight of the edge bd from 17 to 7, and examine the edges again.
Running Prim or Kruskal with G' will output an MST which weighs 27 (actually we have 2 such MSTs {ab, bd, de, cd} and {ab, bd, de, bc}).
But if we use your algorithm, we would get the same exact tree, because when we examine the nodes b or d, the edge bd is not the lightest edge that is adjacent to either one of these nodes.