0
$\begingroup$

Prove if this statement is true: every graph consisting of two edge-disjoint Hamiltonian paths contains a Hamiltonian cycle.

Two edge-disjoint Hamiltonian paths means all vertices can be connected with two different paths of no edges in common; so the graph has at least 2(n-1) edges in total if the graph has n vertices. I am not sure how to relate this to hamilton cycle (how to add one more edge to the path to make it a cycle.)

$\endgroup$
0
$\begingroup$

Consider the graph a = b = c where = represents two edges.
a - b - c, the upper Hamiltonian path and a _ b _ c, the lower Hamiltonian path, are edgewise disjoint.
There is no Hamiltonian cycle.

$\endgroup$
  • $\begingroup$ this is a simple graph theres only one edge $\endgroup$ – james black May 4 at 15:27
  • $\begingroup$ @jamesblack What simple graph? $\endgroup$ – William Elliot May 4 at 22:09

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.