Absolute difference between the sum of incoming and outgoing edges for each vertex is less than or equal to one 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.
 A: Warning: long reasoning ahead. Short version in a commentary below.
Call the number (out degree - in degree) the index of a vertex. I'm assuming  that the graph is finite and connected.
You can assign directions to an undirected graph inductively like this: For two vertices it's easy, just let half of the edges go one way and the other half the other. If there's an odd number of edges between them, one of them will now have index 1, the other -1.
Assume you have directions for all edges within a connected subgraph $S$ and want to find directions for all edges between a vertex $v$ and $S$. Firstfor each vertex of $S$ with more than one edge connected to $v$, label an even number of them in alternating directions. This changes no indexes, and $v$ now only has at most one unassigned edge to any vertex of $S$.
Let $S_-$ be the set of vertices of $S$ connected to $v$ with index $-1$, and define $S_0$ and $S_+$ similarly. For us to be able to assign directions to the edges between $v$ and $S$ we need $\Big||S_+| - |S_-|\Big| \leq |S_0| + 1$. For if this is fulfilled, we assign an edge to go from $v$ to all vertices in $S_+$, to $v$ from all vertices of $S_-$, and use the vertices of $S_0$ to soak up the difference.
Assuming that is is not fulfilled, and further assume wlg that $|S_+| - |S_-| > |S_0| + 1$ (wlg in this case means that were it the other way around, change directions of all edges in $S$) we need a way to alter the directions of edges in $S$ so that it is fulfilled. Now for each vertex of $S_-$, choose a vertex  of $S_+$, and connect each of them to $v$ the obvious way. We're now left with only edges to vertices of $S_+$ and $S_0$ left to assign, and $v$ has a temporary index of $0$. So ignoring the unassigned edges, $S\cup {v}$ is a directed graph satisfying your criterion.
Note that the sum of indexes of the vertices of $S$ is $0$, so the number of vertices with index $1$ and the number of vertices with index $-1$ is the same. I would like to find (and will find in the next paragraph) that for any vertex of $S_+$, you can find a path to a vertex with degree $-1$ (which is not in $S_-$, since that set is now empty). If you can, then swap the direction of all arrows along that path, and you have swapped the index of the two vertices without touching the index of any other vertex. If you now assign directions to the former-$1$-but-now-$(-1)$-index vertex, as well as another vertex of $S_+$ the obvious way, this operation will reduce the number of unassigned edges of $S_+$ by two. Applying the process enough times will make it so that $|S_+| = |S_0|+ 1$ or $|S_+| = |S_0|$, and you can easily assign the rest of the arrows.
Now, assume we're sitting at a vertex $w$ with index $1$. That means we have one more out-going than in-going edges. Let $A_0 = {w}$, and define recursively $A_{n+1}$ to be the union of $A_n$ and the set of vertices pointed to by an edge from $A_n$. That means that $A_n$ is the set of vertices reachable from $w$ by traversing at most $n$ edges along their direction. I want to show that there is a $k$ such that $A_k$ contains a vertex of index $-1$. Let the total index of $A_n$ be the sum of indexes of vertices of $A_n$. As long as $A_n$ does not contain any vertices of index $-1$, it will have at least one edge pointing out of the set. Therefore, $A_{n+1}$ contains a strictly larger set of vertices. If the $A_n$ stops growing, then the total index cannot be positive, so it must contain at least one vertex of index $-1$. But since the graph is finite, the $A_n$'s has to stop growing at some point.
So we've found that there is a path from any vertex of index $1$ to a vertex of index $-1$, we can now swap the direction of any edge along that path, and this will result in the index of those two vertices swapping.
A: I may have a simpler answer:
You add to the input graph $G$ a new vertex $v$ connected to all the vertices in the input graph with an odd degree. The resulting grah $G'$ is what we call Eulerian (all vertices have an even degree). Then you iterate the following step until $G'$ has no edges:
$\bullet$ take a cycle $C$ of $G'$ (In practice, you start from a non-zero degree vertex , go to any of its neighbour and continue until you go back to the one you started from) and you orient the edges of $C$ as a circuit (for a cycle $v_1,v_2,\cdots,v_n$, from $v_1$ to $v_2$, from $v_2$ to $v_3$, ..., from $v_n$ to $v_1$) and then remove the edges of $C$ from $G'$.
Since all vertices of $G'$ have an even degree, when we remove the edges of a cycle, $G'$ remains Eulerian and the degrees of its vertices decrease so the iterations will stop when $G'$ will have no more edges, Hence we have oriented all the edges of $G'$ in such a way that for each of its vertices, the difference between the number of outgoing edges and the number of incoming edges equals zero because for each edge that we oriented to a vertex $u$, we oriented an edge from $u$ as well. Now if we remove $v$, the absolute difference between the number of outgoing edges and the number of incoming edges will remain the same (i.e. 0) for the vertices of even degree in $G$ and will increase to one for the vertices of odd degree in $G$.
A: Hint: First do it in a graph with two vertices
