I want to show the reduction $HC \leq HP$.
Let $G=(V,E)$ be my undirected graph.

My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true for all edges, we have a Hamiltonian circuit in $G$.

It is pretty trivial to proof the first direction (when we have a Hamiltonian circuit in $G$, we will always have a Hamiltonian path in $(V,E\backslash\{e\})$ - independent from the edge we choose).

I really have trouble finding a formal proof for the other direction (either

  1. $\forall e\in E$ Hamiltonian path exists in $(V,E\backslash\{e\})$ $\Rightarrow$ Hamiltonian circle exists in $G$ or

  2. There is no Hamiltonian circle in $E$ $\Rightarrow$ $\exists e \in E:$ $(V,E\backslash\{e\})$ has no Hamiltonian path

  • $\begingroup$ Note that we normally require Karp reductions, but you're using a Cook reduction. (That is, we normally require the reduction to produce a single graph $G'$ such that $G'\in HP$ iff $G\in HC$, whereas you've produced a sequence of graphs $G_1, \dots, G_m$ and are hoping to prove that $G\in HC$ iff $G_i\in HP$ for all $i$.) $\endgroup$ – David Richerby Aug 6 '18 at 16:00
  • $\begingroup$ You could merge all the $G_i$ in one graph, but this only increases the complexity of my explanation. That's why I kept it as short as possible. $\endgroup$ – BlobbyBob Aug 6 '18 at 16:05

Here is a counter example:

take the graph $G=(V,E)$ which is a path


and add two edges to it $e_1=\left\{v_1,v_4\right\}$, $e_2=\left\{v_2,v_5\right\}$.

Verify that $G \notin HC$, but $\forall e \in E$, $\left(V,E\setminus \left\{e\right\}\right) \in HP$


Does a graph have a hamiltonian cycle if for anyone of its edges, it has a hamiltonian path after the removal of that edge?

Note that any hypohamiltonian graph must be such a graph. Is it even true that every hypohamiltonian graph has a hamiltonian cycle?

Not necessarily.

A counterexample is the Peterson graph, which is hypohamiltonian but not hamiltonian.

  • 1
    $\begingroup$ A hypohamiltonian graph becomes hamiltonian if you remove one vertex, not one edge. I haven't tried to find a counterexample but I'm pretty sure the two aren't equivalent. $\endgroup$ – Draconis Aug 6 '18 at 20:15
  • $\begingroup$ @Draconis, thanks for pointing out my lapse. Updated. $\endgroup$ – Apass.Jack Aug 6 '18 at 21:03

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.