4
$\begingroup$

I am trying to prove that an algorithm can be devised to guarantee that absolute value of the difference between the sum of incoming edges and outgoing edges for each vertex is less than or equal to $1$. The in and out edges for each vertex have to be played with.

Note: We cannot delete an edge and can only play with the direction, incoming can be converted to outgoing and vice-versa.

  • 0
    You'll need to specify what sorts of operations you want to allow. If anything goes, then a trivial solution is to remove all the edges.2012-09-20

3 Answers 3