CVRP and removing edges from a graph I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances.
I know that, in general, the complexity of the problem in terms of the number of variables (and computational time) increases with the number of edges in the graph.
I also know that for particular graphs where node degree is fixed (for example 3 or 4), polynomial-time algorithms exist that return the optimal solution.
Therefore, I am playing around with removing the edges with the highest weight from the graph, while ensuring each node retains at least a minimum degree, and seeing how this impacts solution time. As expected, reducing the number of edges in the graph does impact the solution time significantly.
Are there any theoretical results that tie this idea of removing edges from the graph before solving the problem to the optimality of the solution? Is it in some cases possible to conclude, a-priori, that some specific edge will necessarily NOT be part of the optimal solution?
I don't know anything about routing, so take this with a grain of salt.
What you have is a metric graph, in that your graph satisfies the triangle inequality.  If you start removing edges, then  heuristic algorithms might have less to work with, which isn't obviously better.
Take for example a look at these questions:

Bottleneck TSP with MST
For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X


Taking removing edges to the extreme is actually how Christofides algorithm works for approximating Travelling Salesman; Namely by finding a Minimum Spanning Tree and deleting all the remaining edges.