# Why does Hierholzer's algorithm have a time complexity of O(E) instead of O(V+E)?

I saw on Wikipediathat Hierholzer's algorithm has a time complexity of O(E), but won't the dfs used in this algorithm would cause the total time complexity to be O(V+E) instead of only O(E). Assuming we performed the dfs on an Adjacency list. Assume the graph is a connected graph with only one component.

Thanks for the help.

The only interesting case is $$E \in o(|V|)$$ (otherwise you already have $$O(|V|+|E|) = O(|E|)$$).
Then there are at most $$O(|E|)$$ non isolated vertices. You can find the set $$S$$ of these vertices (and hence construct the subgraph induced by $$S$$) in time $$O(|E|)$$ by simply creating an array (of size at most $$2|E|$$) containing all endpoints of the edges in $$E$$, sorting them (in linear time), and dropping the duplicates (again, in linear time).
Then you can apply the algorithm on the remaining subgraph with has $$\Theta(|E|)$$ vertices and $$|E|$$ edges (besides, if the number of remaining vertices is larger than $$|E|+1$$, then the graph has at least two connected components containing at least one edge each, hence no Eulerian path exists).
• No, there are graphs with $|E|=o(|V|)$ that admit an Eulerian path. However, these graphs have isolated vertices. Once you remove then then you are left with $V \le 2|E|$, i.e., $|E| \ge |V|/2$ and hence $O(|V|+|E|)=O(|E|)$. Feb 10, 2022 at 18:58
• I see that you added "Assume the graph is a connected graph with only one component". In this case you clearly have $|E| \ge |V|-1$ (otherwise the graph won't be connected) and hence $O(|V|+|E|) = O(|E|)$. Feb 10, 2022 at 19:01