Recall that an Eulerian trail in a directed graph exists if and only if at most one vertex has (out-degree) − (in-degree) = 1 (start), at most one vertex has (in-degree) − (out-degree) = 1 (end), and all other vertices have equal in-degree and out-degree. How does this apply to finding an Euler tour (circuit)?

Consider the underlying undirected graph formed by ignoring edge directions. If this undirected graph is connected and every vertex has even degree, does that guarantee the existence of an Eulerian circuit in the directed graph? Why or why not?

Suppose the directed graph has an Eulerian circuit. How can you modify Hierholzer’s algorithm (originally for undirected graphs) to traverse edges in their given directions while constructing the circuit? What data structures would you use to track visited edges efficiently?