Solve Hamilton Circuit with Hamilton Path

Question

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

Answer 1

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$

Answer 2

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.