# What is the term for a graph in which each edge belongs to a Hamiltonian cycle?

Furthermore, are they any known results about these graphs, such as necessary or sufficient conditions for a graph to have this property?

A slightly stronger condition is that for any two vertices $$s,t$$ (whether or not $$st$$ is an edge) there is a Hamiltonian path starting at $$s$$ and ending at $$t$$, and such graphs are called Hamiltonian connected.

(All Hamiltonian connected graphs have your property as well: if $$st$$ is an edge, then the Hamiltonian $$s,t$$-path together with that edge forms a Hamiltonian cycle connecting $$st$$. The reverse is not necessarily true.)

Many of the Bondy–Chvátal-type theorems (such as Dirac's theorem and Ore's theorem) for Hamiltonian cycles generalize to prove that a graph is Hamiltonian connected, or to prove your condition. For example, here is a very general result:

Let $$G = (X,E)$$ be a simple graph of order $$n$$ with degrees $$d_1 \le d_2 \le \dots \le d_n$$. Let $$q$$ be an integer, $$0 \le q \le n-3$$. If, for every $$k$$ with $$q < k < \frac12(n+q)$$, the following condition holds: $$d_{k-q} \le k \implies d_{n-k} \ge n-k+q$$ then for each subset $$F$$ of edges with $$|F|=q$$ such that the connected components of $$(X,F)$$ are paths, there exists a Hamiltonian cycle of $$G$$ that contains $$F$$.

Furthermore, this result is the best possible in the following sense: each sequence of degrees that does not satisfy the condition above is majorized by a sequence of degrees of a graph that does not have the desired property.

Take $$q=1$$ and the property in the theorem is exactly the property you want.

This is Theorem 8 in Chapter 10 of Berge's Graphs and Hypergraphs, which follows it by a list of many corollaries you may also be interested in.