# Finding a Hamiltonian cycle from perfect matching of a bipartite graph

A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original graph edges replaced by corresponding L-> R edges.

Is it possible to find a Hamiltonian cycle in G (assuming it exists) as one realization of the vertex-disjoint cycle cover from the bipartite graph, H, using a matching algorithm?

If $$G$$ has a disjoint vertex cycle cover then I agree that $$H$$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $$H$$ exactly). I think the construction you were thinking of is the one described in this answer: https://cstheory.stackexchange.com/a/8570/38111.
As for your question (assuming that $$H$$ is now the bipartite graph constructed in the answer I linked), I think it depends on what you are asking exactly:
• if you are asking "if there is a Hamiltonian cycle in $$G$$, then is there a perfect matching in $$H$$ that 'corresponds' to this cycle" then yes, since, as David Eppstein points out in his answer, the perfect matchings of $$H$$ correspond 1-for-1 with cycle covers of $$G$$, and a Hamiltonian cycle is in particular a vertex disjoint cycle cover.
• Yes. But with a PTIME algorithm $A$ for perfect matching on $H$, you are only guarantied to find a perfect matching of $H$, not all of them, so there is no contradiction here. In other words, you cannot expect that the perfect matchings that $A$ outputs will contain one that corresponds to a Hamiltonian cycle of $G$, unless P=NP. Now, maybe this technique works if you restrict the class of graphs $G$ that you consider in the first place. – M.Monet May 17 '19 at 15:11