MathDB

We have a bipartite graph

G

(with parts

X

and

Y

). We orient each edge arbitrarily. Hessam chooses a vertex at each turn and reverse the orientation of all edges that

v

is one of their endpoint. Prove that with these steps we can reach to a graph that for each vertex

v

in part

X

\deg^{+}(v)\geq \deg^{-}(v)

and for each vertex in part

Y

\deg^{+}v\leq \deg^{-}v

Problem Statement