4
$\begingroup$

Given a directed graph such that at least an Eulerian path exists, how to determine efficiently if there is exactly one Eulerian path?

Of course if there is an Eulerian circuit then there is more than one Eulerian path, so we will assume that no Eulerian circuit exists. In other words, just to fix some notation, we assume that for all nodes $\text{indegree}=\text{outdegree}$ except for two nodes $r$ (starting point) and $s$ (ending point) for which the following holds: $$\text{outdegree}(r) = \text{indegree}(r)+1$$ and $$\text{indegree}(s) = \text{outdegree}(s)+1.$$

An observation. If there is a node with $\text{outdegree} \geq 3$ then there are at least two distinct Eulerian paths. Is this condition only sufficient or maybe even necessary?

$\endgroup$
1
$\begingroup$

Do you know an algorithm for finding Eulerian paths? Fleury's algorithm begins at one of the endpoints and draws out the eulerian path one edge at a time, then imagine removing that edge from the graph. The only trick to the algorithm is that it never chooses an edge that will disconnect the graph. Only with that condition, it is guaranteed to never get stuck in tracing out an eulerian path. So, as long as that choice of edge is unique at every step, the eulerian path will be unique. If ever there are two choices that can be made which are valid (i.e. they each would not disconnect the graph) then you have multiple eulerian paths.

$\endgroup$
  • $\begingroup$ Didn't know this algorithm, thank you $\endgroup$ – Nisba Dec 8 '17 at 17:38
0
$\begingroup$

The condition you give is not necessary. Consider the following graph:

There are two Eulerian paths $A\rightarrow B\rightarrow C\rightarrow A\rightarrow E\rightarrow B\rightarrow D\rightarrow E$ and $A\rightarrow E\rightarrow B\rightarrow C\rightarrow A\rightarrow B\rightarrow D\rightarrow E$, but out-degree of each node is no more than $2$.

We now focus on graphs where out-degree of each node is no more than $2$.

Add an edge from $s$ to $r$ to form a new graph $G$, then there is exactly one Eulerian path if and only if there is exactly one Eulerian cycle in the new graph. According to BEST theorem, the number of Eulerian cycles equals $t_w(G)\prod_{v\in V}(\deg(v)-1)!=t_w(G)$ (note out-degree of each node is no more than $2$ by assumption), where $t_w(G)$ is the number of arborescences of $G$, and can be computed by computing a determinant according to Kirchhoff's theorem.

To summarize, let $Q$ be the Laplacian matrix of $G$, and $Q'$ be the matrix got by deleting the $i$-th column and the $i$-th row (any $i$ is OK) from $Q$. Then there is exactly one Eulerian path in the original graph if and only if $|Q'|=1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.