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.

The answer is 2.

1 solution

Sandra Nicole
Nov 2, 2016

Consider the graph with 1 vertex $V$ and no edges. there is a single path on this graph, the path just containing $V$ .

Now, consider the simple graph with 2 vertices ${V_1, V_2}$ , and a single edge between them. this graph again contains a path from $V_1$ to $V_2$ that is both a Hamiltonian and Eulerian path.

Adding one path and one edge to the end of this graph produces a homeomorphism to the base case, thus are not homeomorphically distinct, when continued.

Now, consider a graph that contains a cycle. Any Eulerian path must visit at least one of the vertices in the cycle twice, meaning the path must be not Hamiltonian. Alternatively, any Hamiltonian path must skip one of the edges in the cycle, thus meaning the path is not Eulerian. Thus, there is no graph that contains a cycle that has a path that is simultaneously Eulerian, and Hamiltonian.

Any graph other than these cannot have a Eulerian path, as said graph must have $\gt 1$ singularly connected sub-graphs. Thus, there are only two homeomorphically distinct graphs that contain a path that is both Hamiltonian and Eulerian.

It shouldn't take that much extra, but you probably should mention the cases which aren't a single path and don't have circuits won't be Euler or Hamiltonian. (Also, nitpick: Eulerian and Hamiltonian should always be capitalized.)

Jason Dyer Staff - 4 years, 7 months ago

Nice job getting your problem featured!

Sharky Kesa - 4 years, 6 months ago

Simultaneous Euler and Hamiltonian Paths

The answer is 2.

1 solution

0 pending reports