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)