# Computational complexity of Eulerian and Hamiltonian paths and cycles in (un)directed graphs

Hey Guys I am aware that we can find if there exists a hamilton path in a directed graph in O(V+E) time using topological sorting.

I was wondering if hamilton cycles, euler paths and euler cycles can also be found in O(V+E) time. If so, how do we find them? Also in case of undirected graphs, how do we go about getting these 4 properties from a graph in O(V+E) time?

• Topological sorting can only find a Hamiltonian path in a directed acyclic graph. For directed graphs in general, determining whether or not a Hamiltonian path exists is NP-complete. – Misha Lavrov Nov 15 '17 at 21:12

See the following theorems of a lecture “Round Trips” of our blockcourse “Algorithmic Graph Theory” by Joachim Spoerhase and Alexander Wolff.

Theorem. Let $G = (V,E)$ be an undirected and connected graph.

(i) We can test in $O(E)$ time, if $G$ is Eulerian.

(ii) If $G$ is Eulerian, we can find in $O(E)$ time an Eulerian cycle.

A problem to find an Eulerian path can be reduced to a problem to find an Eulerian cycle as follows. If we have a graph $G$ for which exists an Eulerian path then $G$ has exactly two vertices of odd degree. Add an edge $e$ between these vertices, find an Eulerian cycle on $G+e$ and then remove $e$ from the cycle, obtaining an Eulerian path in $G$.

Theorem. Let $G = (V,E)$ be an directed and weakly connected graph.

(i) We can test in $O(E)$ time, if $G$ is Eulerian.

(ii) If $G$ is Eulerian, we can compute in $O(E)$ time an Eulerian cycle.

Theorem. [Karp, 1972] (Un)directed Hamiltonian cycle and path are NP-hard.