Would removing the max weighted edge from a Hamiltonian circuit result in a Hamiltonian path?

Question

If I have a Hamiltonian circuit, assuming that cutting the max weighted edge resulted in a Hamiltonian path.

Is it guaranteed that the path would be minimal too?

Answer 1

No, for example the graph below.

The minimum Hamilton path uses the edges of weight 2, 1 and 4. However, the only Hamilton cycle uses the edges of weight 2, 3, 4 and 5, so removing the maximum-weight edge does not give a minimum Hamilton cycle.

Answer 2

If a Hamiltionian path is simply any path that visits all vertices, then removing any edge from a Hamiltonian circut results in a Hamiltonian path.

But I assume you want the shortest one, in which case the answer to your question is No.

Take for example a square with one diagonal, i.e. something like this:

A --B
|  /|
| / |
|/  |
C---D

Now, put a large weight on the edges $BD$ and $AC$. That way, the shortest path going through all vertices is A-B-C-D, but the shortest (and only) cycle is still A-B-D-C.

Answer 3

I presume your circuit is a Hamiltonian circuit of minimum weight. Then removing any edge of the circuit will produce a Hamiltonian path from one vertex of the removed edge to the other, and it will have minimum weight among Hamiltonian paths between those two vertices (because if you had a lower-weight Hamiltonian path between those two, adding back the removed edge would give you a lower-weight Hamiltonian cycle). However, it need not have minimum weight among all Hamiltonian paths (see the other answers).