Orientation of a graph

A choice of direction for each edge of an undirected graph, producing a directed graph.

A finite undirected graph can be oriented with outdegree at least an integer $k\ge 0$ at every vertex if and only if every vertex subset $U$ is incident to at least $k|U|$ distinct edges. The max-flow min-cut theorem and integral max-flow theorem prove sufficiency by assigning distinct edges to vertices through an incidence flow network; each assigned edge is oriented away from that vertex. Necessity follows by counting outgoing edges from $U$.