HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove every well-balanced orientation of an Eulerian graph is Eulerian?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#2046, answer score: 5

Revisions (0)

No revisions yet.