0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

No, for example the graph below.

enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.