Do All Hamiltonian Paths in a Graph with Several Disjoint Ham-Paths Have the Same Number of Edges?

130 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.