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$

1 Answer 1

Reset to default
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$
2
  • $\begingroup$ this is a simple graph theres only one edge $\endgroup$
    – james black
    Commented May 4, 2019 at 15:27
  • $\begingroup$ @jamesblack What simple graph? $\endgroup$
    – William Elliot
    Commented May 4, 2019 at 22:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .