I maybe thought about the problem in a more general way, which makes the proof verbose. But I think it’s somewhat intuitive.
First, I guessed that the following property holds:
Property Suppose a connected component has n edges.
- if n is even, you can orient the edges so that every node has an even outdegree
- if n is odd, you can orient the edges so that exactly one node has an odd outdegree
You can prove this by induction. For example, consider case where n is even. Pick a random edge, orient it arbitrarily, and remove it from the graph. There are two possibilities:
- The graph remains one component, in which case we can orient the edge arbitrarily and by induction there exists a way to finish orienting the edges so that all outdegrees are even
- The graph splits into 2 components (i.e. the edge removed was a bridge), one with an odd number of edges and one with an even number of edges. Then orient the removed edge towards the component with an odd number of edges and again by induction there exists a way to finish orienting the edges so all out degrees are even.
Then for the algorithm, it’s too complicated to implement the above, (although it’s doable with online bridge finding). But the characterization is very convenient–we can consider a leaf of the DFS tree and see that pointing all back edges out and deciding on the direction of the tree edge based on the parity of deg(leaf) will never make an orientable graph unorientable.
Edit: by the way, this characterization of when a graph is orientable answers @hocus_p0cus point about the direction of the backedges not mattering, since we can prove a related property:
Property: In a tree with e edges, you can orient the edges so that vertices v_1, v_2, \dots v_k vertices have odd outdegree, as long as e and k have the same parity.
Proof: We already know how to orient the edges so that either 0 or 1 vertex has an odd outdegree, depending on the parity of e. Orient the vertices accordingly.
Then there are an even number of vertices v_1, v_2, \dots, v_{2m} that need the parity changed.
Simply pair up the vertices and consider the paths v_1\rightarrow v_2, v_3\rightarrow v_4, \dots.
For every path, reverse the orientation of all edges on the path, which changes the parity of the outdegree only of the endpoints. Then the resulting orientation has exactly k vertices of odd outdegree.