4
$\begingroup$

There is a graph G, which is not known to me. Instead I am given the multiset of all graphs that are obtained by deleting a single vertex from G. My task is to figure out, from all of these subgraphs, whether the original graph G has a Hamiltonian cycle.

My original idea was to assert that, if all of these subgraphs have Hamiltonian paths, then G has a Hamiltonian cycle - but it was pointed out that my reasoning was flawed and this is not actually the case (for example, all such subgraphs of the Petersen graph have Hamiltonian paths, but the Petersen graph does not have a Hamiltonian cycle). And this is where I'm stuck. How could I get to the answer?

(full disclosure - this is a homework exercise)

|cite|improve this question
$\endgroup$
  • $\begingroup$ From all these graphs you can reconstruct the original graph, no? $\endgroup$ – Pål GD Jan 13 '15 at 17:25
  • $\begingroup$ @PålGD - I highly doubt it :). Even reconstructing a graph from the entire set of subgraphs (resulting from deletion of any non-empty subset of vertices) is still a major open problems of graph theory. $\endgroup$ – R B Jan 13 '15 at 18:57
  • $\begingroup$ @RB On non-labelled graphs, then? $\endgroup$ – Pål GD Jan 13 '15 at 19:13
  • $\begingroup$ @PålGD - yes, but I figured this was the intent since he was mentioned a multiset of subgraphs. $\endgroup$ – R B Jan 13 '15 at 19:22
  • $\begingroup$ @RB good point. $\endgroup$ – Pål GD Jan 13 '15 at 19:25

Your Answer

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

Browse other questions tagged or ask your own question.