I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same outgoing and incoming degree.
1 Answer
If such an orientation is possible, then all degrees are even. Conversely, if all degrees are even then the graph is Eulerian. Orient the edges according to an Eulerian circuit.