## 3 Parsimonious Property for Directed Eulerian Graphs
### Connectivity and the Splitting Operation
**Lemma 3**: _Let \(s\) be any node of \(G\) and let \(u\) be any outneighbor of \(s\). Then there exists another inneighbor of \(s\), say \(v\), such that, by splitting \((s,u)\) and \((v,s)\), i.e., removing the arcs \((s,u)\) and \((v,s)\) and adding the arc \((v,u)\), we obtain a multigraph \(G^{\prime}\) satisfying the following conditions:_1. \(p_{G^{\prime}}(i,j)=p_{G}(i,j)\) _for all_ \(i,j\in V\setminus\{s\}\) _and_
2. \(p_{G^{\prime}}(s,j)=\min(p_{G}(s,j),d_{G}^{+}(s)-1)\)_._  
Our proof for Lemma 3 is very similar to the [PERSON] proof for Lemma 1. This latter is also in major part inspired from the one of [PERSON] for Lemma 1 (Condition 1) which proceeds along the following lines. 1. There exists at most one set \(S\) satisfying: **(a1)**: \(s\in S\), \(u\
otin S\), **(b1)**: \(|\delta_{G}(S)|=c_{G}(i,j)\) for some \(i,j\in V\), \(i\in S\), \(j\
otin S\) and \(i\
eq s\) and **(c1)**: \(S\) is minimal with respect to the above two conditions. 2. If there is no such \(S\), then any neighbor \(v\) of \(s\) can be used for the splitting operation. 3. If such a \(S\) exists then there exists at least one neighbor of \(s\) in \(S\). Moreover, any neighbor of \(s\) in \(S\) can be used for the splitting operation. We will show that this proof procedure can be used for the directed case. Let us remove the orientation on the arcs of \(G\), then \(G\) becomes an undirected Eulerian multigraph. The following remark expresses the relation between \(c_{G}(i,j)\), which is the number of edge-disjoint paths between \(i\) and \(j\) in undirected \(G\), and \(p_{G}(i,j)\), which is the number of arc-disjoint paths from \(i\) to \(j\) (or \(p_{G}(j,i)\) for the number of arc-disjoint paths from \(j\) to \(i\)) in the original directed graph \(G\). **Remark 1**: _Let \(\delta_{G}(S)\) be the cut associated to \(S\) in the undirected \(G\). We have_  
* \(|\delta_{G}(S)|=2|\delta_{G}^{+}(S)|=2|\delta_{G}^{-}(S)|\) _for all_ \(S\subset V\)_._
* \(c_{G}(i,j)=2p_{G}(i,j)=2p_{G}(j,i)\)_._  
We have \(\delta_{G}(S)=\delta_{G}^{+}(S)\cup\delta_{G}^{-}(S)\) and as \(\delta_{G}^{+}(S)\cap\delta_{G}^{-}(S)=\emptyset\), \(|\delta_{G}(S)|=|\delta_{G}^{+}(S)|+|\delta_{G}^{-}(S)|\). Since \(G\) is Eulerian, we have \(|\delta_{G}^{+}(S)|=|\delta_{G}^{-}(S)|\) for all \(S\subset V\). Hence, \(|\delta_{G}(S)|=2|\delta_{G}^{+}(S)|=2|\delta_{G}^{-}(S)|\). For all pair \(i\), \(j\) in \(V\) with \(i\
eq j\), as \(p_{G}(i,j)=\min\{|\delta^{+}(T)|\ :\ \ i\in T\text{ and }j\in V\setminus T\}\), \(p_{G}(j,i)=\min\{|\delta^{-}(T)|\ :\ \ i\in T\text{ and }j\in V\setminus T\}\) and \(|\delta_{G}^{+}(T)|=|\delta_{G}^{-}(T)|\) for all \(T\subset V\), we have \(p_{G}(i,j)=p_{G}(j,i)\) and \(c_{G}(i,j)=2p_{G}(i,j)=2p_{G}(j,i)\). Hence, given any \(s\in V\), applying the [PERSON]'s procedure for undirected \(G\), we have  
* either there exists exactly a \(S\) satisfying **(a1), (b1)** and **(c1)**. Reconsider \(S\) in the original directed \(G\), we prove that \(S\) satisfies **(a2)**: \(s\in S\), \(u\
otin S\), **(b2)**: \(|\delta_{G}^{+}(S)|=p_{G}(i,j)\) for some \(i,j\in V\), \(i\in S\), \(j\
otin S\) and \(i\
eq s\) and **(c2)**: \(S\) is minimal with respect to the above two conditions. Indeed, by Remark 1, if \[u\in V\]5 then \[u\in V\]6 The conditions **(a1)** and **(a2)** (or **(c1)** and **(c2)**, respectively) are the same, independent from the fact that \(G\) is directed or not. * otherwise, _i.e._, no \(S\) satisfying **(a1), (b1)** and **(c1)** exists. Then for all \(S\subset V\) such that \(s\in S\) and \(u\
otin S\), we have \(|\delta_{G}(S)|>c_{G}(i,j)\) for all \(i,j\in V\), \(i\in S\), \(j\
otin S\) and \(i\
eq s\). By \(|\delta_{G}(S)|=2|\delta_{G}^{+}(S)|=2|\delta_{G}^{-}(S)|\), we have also in the original directed graph \(G\), \(|\delta_{G}^{+}(S)|>p_{G}(i,j)\) for all \(i,j\in V\), \(i\in S\), \(j\
otin S\) and \(i\
eq s\). Hence, we can select any inneighbor \(v\) of \(s\) and split \((s,u)\) and \((v,s)\) without changing the value of \(p_{G}(i,j)\) for all \(i,j\in V\setminus\{s\}\).