# Simultaneous Euler and Hamiltonian Paths

How many homeomorphically distinct graphs exist such that they contain a path that is both Eulerian and Hamiltonian?

Definitions:

• A walk on a graph is a sequence $$(v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_k)$$, where $$v_0, v_1, \ldots, v_k$$ are vertices of the graph, $$e_1, e_2, \ldots, e_k$$ are edges of the graph, and $$e_i = \{v_{i-1}, v_i\}$$ for all $$i = 1, 2, \ldots, k$$.
• An Eulerian path is a walk that uses each edge exactly once. That is, $$e_1, e_2, \ldots, e_k$$ are all distinct, and they are exactly the edges of the graph in some order.
• A Hamiltonian path is a walk that uses each vertex exactly once. That is, $$v_0, v_1, \ldots, v_k$$ are all distinct, and they are exactly the vertices of the graph in some order.
• A subdivision of an edge $$e = \{u,v\}$$ in a graph gives a modified version of the graph, having an additional vertex $$w$$ and two additional edges $$\{u,w\}, \{v,w\}$$, and missing the original edge $$e$$. A subdivision of a graph is the result of subdividing any number of the edges of the graph. (An edge that's the result of some earlier subdivision may still be subdivided.)
• Two graphs $$G, G'$$ are homeomorphic if there is some graph $$H$$ that is both isomorphic to a subdivision of $$G$$ and isomorphic to a subdivision of $$G'$$. Informally, if $$G$$ and $$G'$$ are drawn with vertices as invisible points and edges as arcs, then two homeomorphic graphs "look the same." Two graphs are homeomorphically distinct if they are not homeomorphic.
×