0
$\begingroup$

I understand that a HAM-Path must cover all vertices without necessarily touching all edges. But, if a graph has, lets say, 2 edge-disjoint HAM-Paths, will both of these paths touch the same amount of edges?

In a sense, it makes sense, but I am not quite sure. I can't find a lot of literature on the issue.

Will this always hold?

$\endgroup$
0
$\begingroup$

Any path on $n$ vertices has $n-1$ edges. (Indeed, any tree on $n$ vertices has $n-1$ edges.) A Hamiltonian path is simply a path that happens to contain every vertex of its host graph, so all Hamiltonian paths of a given graph contain the same number of edges.

$\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.