snippetMinor
How to prove every well-balanced orientation of an Eulerian graph is Eulerian?
Viewed 0 times
graphorientationeverybalancedprovewellhoweulerian
Problem
I'm trying to prove that every well-balanced orientation of an Eulerian graph is Eulerian.
I want to prove it by showing that for any two vertices $u$ and $v$, their local arc connectivities coincide, that is
$\qquad \displaystyle P_D'(u,v)=P_D'(v,u)$
for every well-balanced orientation of an Eulerian graph. How can I do this?
I want to prove it by showing that for any two vertices $u$ and $v$, their local arc connectivities coincide, that is
$\qquad \displaystyle P_D'(u,v)=P_D'(v,u)$
for every well-balanced orientation of an Eulerian graph. How can I do this?
Solution
Your statement follows from Corollary 1 in
L Lovász, Connectivity in digraphs, Journal of Combinatorial Theory, Series B, Volume 15, Issue 2, October 1973, Pages 174-177
The Corollary says, that if you have a vertex $u$, and for every other vertex $v$ the number of edge-disjoint paths from $u$ to $v$ equals the number of edge-disjoint paths from $v$ to $u$, then we have $\text{indegree}(u)=\text{outdegree}(u)$. Since the statement is true for every vertex of the graph, the orientation is Eulerian.
The proof of the corollary and its corresponding theorem is rather technical, but self-contained, and needs less than two pages.
L Lovász, Connectivity in digraphs, Journal of Combinatorial Theory, Series B, Volume 15, Issue 2, October 1973, Pages 174-177
The Corollary says, that if you have a vertex $u$, and for every other vertex $v$ the number of edge-disjoint paths from $u$ to $v$ equals the number of edge-disjoint paths from $v$ to $u$, then we have $\text{indegree}(u)=\text{outdegree}(u)$. Since the statement is true for every vertex of the graph, the orientation is Eulerian.
The proof of the corollary and its corresponding theorem is rather technical, but self-contained, and needs less than two pages.
Context
StackExchange Computer Science Q#2046, answer score: 5
Revisions (0)
No revisions yet.