= Outdegree orientation criterion
{title2=$d(U)\geq k|U|$}
A finite undirected <graph> can be oriented with <outdegree> at least an integer $k\geq0$ 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$.
Back to article page
