I am trying to find an algorithm with polynomial run time that calculates the lower bound of the optimal solution on the Hamiltonian Path problem( a lower bound to the sum weight of the hamiltonian path).
My first thought was to place the edges in ascending order and pick one edge at a time. But this is like kruskal. Any ideas might be helpful
Yes, because a Hamiltonian path is a spanning tree, computing a minimum spanning tree (MST) provides a lower bound on every Hamiltonian path. And you can compute a MST in polynomial time. Here, you are enforcing connectivity but relaxing the degree-2 constraints.
Another polynomially computable lower bound arises from using a dummy node to convert to Hamiltonian tour and then solving an assignment problem to find a minimum-weight union of cycles. Here, you are enforcing the degree-2 constraints but relaxing connectivity.