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

Problem Loading...

Note Loading...

Set Loading...