# Simultaneous Euler and Hamiltonian Paths

Probability Level 5

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.
×

Problem Loading...

Note Loading...

Set Loading...