How many homeomorphically distinct graphs exist such that they contain a path that is both Eulerian and Hamiltonian?
- A walk on a graph is a sequence , where are vertices of the graph, are edges of the graph, and for all .
- An Eulerian path is a walk that uses each edge exactly once. That is, 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, are all distinct, and they are exactly the vertices of the graph in some order.
- A subdivision of an edge in a graph gives a modified version of the graph, having an additional vertex and two additional edges , and missing the original edge . 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 are homeomorphic if there is some graph that is both isomorphic to a subdivision of and isomorphic to a subdivision of . Informally, if and 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.