I was wondering if this is already a solved question, it would save me a bunch of time if it is.
Is it the case that in an undirected hamiltonian graph with N nodes, if some subset of our N nodes has more edges than another subset of nodes, that we can remove the extra edges without destroying the hamiltonicity of our graph?
For example say we have a graph with 12 nodes and 41 edges, and every node has at least 3 edges. We can easily reduce this to a cubic graph by simply finding the edges (i,j) where both i and j have greater than 6 instances of being the front or back of the edge.
So then my question is: would eliminating such edges ever result in destruction of the hamiltonicity of the graph?
First of all, you cannot necessarily reduce a graph with minimum degree $3$ to a cubic graph just by deleting edges between two vertices of degree $>3$.
For example, consider the complete bipartite graph $K_{3,9}$. Here, all vertices have degree at least $3$, and some of them have degree $9$. But we can't create a cubic graph by deleting edges, because deleting any edge will bring some vertex's degree down to $2$.
Second, under some conditions, you can guarantee that a Hamiltonian graph remains Hamiltonian after you delete an edge between two high-degree vertices. By the converse of the Bondy–Chvátal theorem, if you have a Hamiltonian graph $G$ on $n$ vertices and you delete an edge $uv$ such that $(\deg u - 1) + (\deg v - 1) \ge n$ (that is, $\deg u + \deg v \ge n$ in the resulting graph $G-uv$) then $G-uv$ remains Hamiltonian.
But if your goal is to reduce a $12$-vertex graph to a cubic graph, then if you do succeed you will be deleting edges at the end with $\deg u = \deg v = 3$ after deletion. This does not satisfy the condition of the Bondy–Chvátal theorem, so you may end up destroying all Hamiltonian cycles this way. (It's even possible that in the process of deleting edges to create a cubic graph, you disconnect the graph.)