# Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given an undirected graph $$G=(V,E)$$, describe an algorithm that computes an orientation of $$E$$ such that each vertex has out-degree at least 3.

I know how to check if a vertex $$v$$ has at least $$k$$ edge-disjoint paths to any other vertex (using Ford-Fulkerson), so I thought I may use that for $$k=3$$.

Given $$G=(V,E)$$, create a directed bipartite graph $$H=(V+E, F)$$ where there is an edge $$(v,e) \in F$$ iff $$v \in V$$ is an endpoint of $$e \in E$$. All these edges have capacity $$1$$.
Augment $$H$$ as follows: add two additional vertices $$s$$ and $$t$$; for each $$v \in V$$ add an edge $$(s,v)$$ with capacity $$3$$; for each $$e \in E$$ add the edge $$(e, t)$$ with capacity $$1$$.
Compute a maximum flow $$\phi$$ from $$s$$ to $$t$$ in the augmented version of $$H$$. Your problem admits a solution if and only if the amount of flow $$|\phi|$$ is $$3|V|$$.
To see this, first observe that $$3|V|$$ is an upper bound on $$|\phi|$$. Then suppose that there exists a feasible orientation $$\mathcal{O}$$ and look at any partial orientation $$\mathcal{O}'$$ in which each vertex $$v$$ has exactly three outgoing edges. A flow $$\phi$$ such that $$|\phi|=3|V|$$ is obtained by sending one unit of flow across each edge $$(v,e) \in F$$ such that $$e$$ is oriented away from $$v$$ in $$\mathcal{O}'$$, the flow across each edge $$(s,v)$$ is $$3$$, and the flow across $$(e,t)$$ is 1 if $$e$$ is oriented in $$\mathcal{O}'$$ and $$0$$ otherwise.
Suppose now that there is a flow $$\phi$$ such that $$|\phi|=3|V|$$. W.l.o.g., $$\phi$$ is integral. A feasible orientation is obtained by orienting each edge $$e \in E$$ away from the (at most one) endpoint $$v$$ of $$e$$ for which $$\phi(v,e)=1$$. If no such endpoint exists, then $$e$$ can be oriented arbitrarily. Notice that this procedure is constructive and immediately yields an algorithm for your problem.