# Solve Hamilton Circuit with Hamilton Path

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

• 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$.) – David Richerby Aug 6 '18 at 16:00
• 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. – BlobbyBob Aug 6 '18 at 16:05

Here is a counter example:

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

$v_1-v_2-v_3-v_4-v_5$

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.

• 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. – Draconis Aug 6 '18 at 20:15
• @Draconis, thanks for pointing out my lapse. Updated. – John L. Aug 6 '18 at 21:03