Every digraph of positive minimum outdegree contains a directed cycle. Thus a one-sided degree condition already forces a subdigraph with positive degrees in both directions. The corresponding quantitative question is less immediate: if every vertex has at least $d$ outneighbors, how large a minimum indegree and minimum outdegree can be guaranteed on a common set of vertices? Deleting vertices of small indegree is a natural first step, but it also removes outneighbors of the vertices that remain. The problem is to control this loss using only the original outdegree condition.

We consider finite loopless digraphs with at most one arc in each ordered direction between distinct vertices. Both opposite arcs may be present; such a pair is called a digon. For a nonempty digraph $G$, write $d_G^{+}(v)$ and $d_G^{-}(v)$ for the outdegree and indegree of $v$, and define

The extraction parameter is

Allowing arbitrary subdigraphs gives the same maximum, since completing a subdigraph to the induced subdigraph on its vertex set cannot decrease its degrees. A hypothesis beyond arc density is necessary: a transitive tournament has $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ arcs and $q(G)=0$. Degree balance permits extraction from arc density in Eulerian digraphs [5]; here no balance between the two directions is assumed.

Grzesik, Rödl, and Volec [4, Theorem 1.1] proved that every $n$-vertex digraph with ${\delta }^{+}(G)\ge d$ satisfies

Their tournament constructions establish the sharp leading constant in the small-density regime. For $d$ proportional to $n$, they gave additional estimates and asked for the optimal normalized bound [4, Problem 1]. We determine the finite extremum, including the correction that becomes significant at positive density.

For integers $n\ge 1$ and $0\le d\le n-1$, put

and define

The integer $c=d$ satisfies this inequality, so $0\le C(n,d)\le d$.

For the dense problem, fix , set $N_{\alpha }=\lceil {(1-\alpha )}^{-1}\rceil$, and for $n\ge N_{\alpha }$ define

The restriction on $n$ is precisely the feasibility condition $\lceil \alpha n\rceil \le n-1$. Integrality of the degrees and the induced-subdigraph reduction show that this is the function in [4, Section 4.1].

The previous dense estimates were

For example, at minimum outdegree $4n/5$, these estimates guarantee asymptotically $(1-\sqrt{11}/5)n\approx 0.337n$, whereas the sharp leading term is $2n/5$. The difference comes from retaining the quadratic term $c(c+1)/2$ in (1.4). Omitting it recovers (1.2); retaining it changes the leading answer when $c$ is linear in $n$.

The lower bound uses the mixed deletion procedure of [4, Section 2]: if no subdigraph has minimum semidegree greater than $c$, repeatedly delete a vertex with indegree or outdegree at most $c$. The difficulty is that the controlled direction may change from one deletion to the next. We mark the direction controlled on each vertex pair. The unmarked possible directions nevertheless form a transitive tournament, with outdegrees $0,1,\mathrm{\dots },n-1$. Whatever arcs of the original digraph occur in these directions, the marked directions must supply at least $d+(d-1)+\cdots +1$ further outgoing arcs. Counting their capacity exactly gives (1.4).

Sharpness requires a compatible placement of those arcs. In an ordered construction, backward arcs supply most of the outdegree, leaving forward demands $d,d-1,\mathrm{\dots },1$. Capping the forward indegree at $c$ ensures that the largest vertex of every induced subdigraph has indegree at most $c$. The total capacity condition is necessary, but a priori smaller sets of demands could encounter tighter bottlenecks. We show that the nested allowed neighborhoods make every such cut no more restrictive than (1.4). An integral flow then places the forward arcs, and backward arcs complete every outdegree to $d$. Sections 2 and 3 prove these two assertions; Section 4 gives the dense limit and its relation to directed degeneracy.

The deletion order and the ambient outdegrees give opposite bounds on one set of arcs. We distinguish possible directions from arcs actually present in the digraph. For a real number $x$, write $x_{+}=\max \{x,0\}$.

Since $q(G)$ is an integer, Proposition 2.1 and the definition of $C(n,d)$ imply

We now realize the two counts in the lower bound simultaneously. Fix integers $n\ge 1$ and $0\le d\le n-1$, and set $c=C(n,d)$. For $d=0$, take $G_{n,0}$ to be the edgeless digraph, so $q(G_{n,0})=0=c$. Assume henceforth that $d\ge 1$, so $1\le c\le d$.

Order the vertices as $[n]=\{1,\mathrm{\dots },n\}$. An arc $i\to j$ is forward if , and backward if $i>j$. A vertex $i\le d$ can use its $i-1$ backward directions but still needs $d-i+1$ forward arcs to reach outdegree $d$. Later vertices can reach outdegree $d$ using backward arcs alone. We choose the required forward arcs so that no vertex receives more than $c$ of them. This will bound the indegree of the largest vertex in every induced subdigraph. The only remaining issue is whether the demands can be met with these capacities at all vertices, not just in total.

Let $G_{n,d}$ start with the forward arcs supplied by Lemma 3.1. For each $i\le d$, add all backward arcs $i\to j$ with . For each $i>d$, add the arcs $i\to j$ for $1\le j\le d$; these are backward because . There are no other arcs. For $i\le d$, the resulting outdegree is

and every $i>d$ has exactly the $d$ added backward out-arcs. Thus all vertices have outdegree $d$.

For any nonempty $S\subseteq [n]$, let $j=\max S$. Every arc of $G_{n,d}[S]$ entering $j$ is forward, hence belongs to $F$. It follows that

Consequently $q(G_{n,d})\le C(n,d)$, proving the matching upper bound.

The network has $O(n)$ vertices and $O(dn)$ edges. Integral augmentation from zero flow increases its value by at least one per step, so at most $d(d+1)/2$ augmentations suffice. This gives a polynomial-time construction; $c$ can be computed from the integer inequality (1.4) without approximating the square root.

The value in (1.7) strictly improves both lower bounds for every . For the first, rationalization gives $1-\sqrt{1-{\alpha }^2}={\alpha }^2/(1+\sqrt{1-{\alpha }^2})>{\alpha }^2/2$. For the second, the difference between the radicands is $(3-4\alpha +{\alpha }^2)-(1-{\alpha }^2)=2{(1-\alpha )}^2>0$. The exact value is also less than $\alpha$, because $1-{\alpha }^2>{(1-\alpha )}^2$.

At the two endpoints,

The first expansion recovers the sharp leading small-density term and identifies its next correction.

The finite parameter also describes directed degeneracy. Under the convention of [3, 1], a digraph is weakly $k$-degenerate if every nonempty subdigraph has a vertex of indegree or outdegree less than $k$; hence $q(G)\le c$ is equivalent to weak $(c+1)$-degeneracy. The “at most $k$” convention in [2] shifts the index by one.

For oriented graphs, which forbid digons, Proposition 2.1 still applies, but the construction in Section 3 need not be oriented. Thus it does not settle [4, Problem 2]. Normalizing the extracted semidegree by its own order $|V(H)|$, instead of $n$, also gives a different problem [4, Section 4.3].