Proof. A sink satisfies the second-neighborhood inequality, so \(D\) has no sink and has more than one vertex. If \(D\) were not strongly connected, take a strongly connected component with no outgoing arc to another component. All first and second out-neighborhoods of its vertices lie in that component. Its induced graph would therefore be a smaller counterexample, contrary to the choice of \(D\). Thus \(D\) is strongly connected, and every vertex has an in-neighbor.

Fix a nonempty proper subset \(S\) and put \[I=F(S)\cap S,\qquad E=F(S)\setminus S, \qquad g(T)=\lvert F(T)\setminus(I\cup T)\rvert\quad(T\subseteq E).\] Strong connectivity gives \(E\ne\varnothing\). We will enlarge \(T\) from \(\varnothing\) to \(E\) so that the increase in \(g(T)\) is strictly smaller than the number of newly adjoined vertices at every step.

For \(T\subsetneq E\), let \(D_T\) be obtained from the original graph \(D\) by deleting all arcs from \(S\) to \(E\setminus T\). Since every vertex of \(E\setminus T\) receives an arc from \(S\), at least one arc is deleted. Minimality of the number of arcs gives a vertex \(v\) satisfying \(\lvert N_{1,D_T}^+(v)\rvert\le\lvert N_{2,D_T}^+(v)\rvert\). If \(v\) had lost no first out-neighbor, deleting arcs could only shrink its exact second out-neighborhood, so it would still violate this inequality. Consequently \(v\in S\), and the set \[Q=F(\{v\})\cap(E\setminus T)\] is nonempty. It is exactly the set of first out-neighbors that \(v\) loses. The original first out-neighborhood of \(v\) is contained in \(I\cup T\cup Q\), and the remaining first out-neighbors lie in \(I\cup T\).

We compare the exact second out-neighborhoods before and after deletion. A two-step path from \(v\) in \(D_T\) through a vertex of \(I\subseteq S\) ends in \(I\cup T\), since all arcs from \(S\) to \(E\setminus T\) were deleted. A path through a vertex of \(T\) ends in \(F(T)\). Thus \[ F_{D_T}^2(\{v\})\subseteq I\cup T\cup F(T). \tag{4}\] Every newly counted exact second out-neighbor must have been a first out-neighbor in \(D\): deletion creates no paths, and \(v\) itself is never an exact second out-neighbor. Such a vertex lies in \(Q\), and (4), together with \(Q\cap(I\cup T)=\varnothing\), places it in \(Q\cap F(T)\).

On the other hand, define \[C=F(Q)\setminus\bigl(I\cup T\cup Q\cup F(T)\bigr).\] Every vertex of \(C\) was reached from \(v\) in two steps through \(Q\), and none was a first out-neighbor. Also \(v\notin F(Q)\): an arc from a vertex of \(Q\) back to \(v\) would oppose the arc from \(v\) to that vertex. Hence \(C\subseteq N_{2,D}^+(v)\). By (4), no vertex of \(C\) remains reachable in two steps in \(D_T\).

Write \(d_1=\lvert N_{1,D}^+(v)\rvert\) and \(d_2=\lvert N_{2,D}^+(v)\rvert\). The gains and losses just identified imply \[d_1-\lvert Q\rvert \le \lvert N_{2,D_T}^+(v)\rvert \le d_2-\lvert C\rvert+\lvert Q\cap F(T)\rvert.\] The change in \(g\) is exact: adjoining \(Q\) removes the points \(Q\cap F(T)\) from the previously counted image and adds precisely \(C\). Since \(d_2<d_1\), it follows that \[ g(T\cup Q)-g(T) =\lvert C\rvert-\lvert Q\cap F(T)\rvert \le \lvert Q\rvert+d_2-d_1 <\lvert Q\rvert. \tag{5}\]

Starting with \(T=\varnothing\), repeat this step until \(T=E\). Each deletion is performed afresh on the original \(D\), so the same minimality argument applies at every step. Each \(Q\) is a nonempty subset of the part of \(E\) not yet adjoined; hence the process terminates. Summing (5) and using \(g(\varnothing)=0\) gives \(g(E)<\lvert E\rvert\). Finally, \(F(S)=I\cup E\) and \(F(I)\subseteq F(S)\), so \[F^2(S)\setminus F(S) =\bigl(F(I)\cup F(E)\bigr)\setminus(I\cup E) =F(E)\setminus(I\cup E).\] Its cardinality is \(g(E)\), proving (3). ◻

Proof. Label the vertices within each block by \(1,\ldots,m\), with arcs from smaller to larger labels. Let \(f\) be the image operator within this transitive tournament. For a nonempty set \(T\) of labels with least element \(a\), we have \(f(T)=\{a+1,\ldots,m\}\). Thus \[ \lvert T\rvert-\lvert f(T)\rvert\le1,\qquad f^2(T)\subseteq f(T),\qquad \lvert T\rvert-2\lvert f(T)\rvert+\lvert f^2(T)\rvert\le1. \tag{6}\] The construction produces an oriented graph. Every vertex receives arcs from an incoming base block, so all indegrees in \(G\) are positive. Call an arc external if it joins distinct blocks, and internal otherwise.

Fix \(\varnothing\ne U\subsetneq V(G)\). Write \(T_v\) for the labels selected by \(U\) in the block at \(v\), and define its support and a set of base vertices by \[S=\{v\in V(D):T_v\ne\varnothing\},\qquad H_0=F(S)\cup F^2(S).\] Every block indexed by \(F(S)\) is filled by \(F_G(U)\). In each remaining block the first image consists exactly of \(f(T_v)\), so \[\lvert F_G(U)\rvert=m\lvert F(S)\rvert +\sum_{v\in S\setminus F(S)}\lvert f(T_v)\rvert.\] A two-step path using two external arcs ends in an \(F^2(S)\)-block. One using exactly one external arc ends in an \(F(S)\)-block, regardless of the order of its internal and external steps. Paths using only internal arcs contribute \(f^2(T_v)\). Therefore \[\lvert F_G^2(U)\rvert\le m\lvert H_0\rvert +\sum_{v\in S\setminus H_0}\lvert f^2(T_v)\rvert.\] Combining these estimates gives the sharper bound \[\begin{align*} \lvert U\rvert-2\lvert F_G(U)\rvert+\lvert F_G^2(U)\rvert &\le m\bigl(\lvert H_0\rvert-2\lvert F(S)\rvert\bigr) +\sum_{v\in S}\lvert T_v\rvert \\ &\quad -2\sum_{v\in S\setminus F(S)}\lvert f(T_v)\rvert +\sum_{v\in S\setminus H_0}\lvert f^2(T_v)\rvert. \tag{7}\end{align*}\] Since \(F(S)\subseteq H_0\), extending the last sum to \(S\setminus F(S)\) only adds nonnegative terms. This may count internal second images in blocks already bounded by a full block in [eq:blowup-sharp]; it remains a valid upper bound. Now use \(\lvert T_v\rvert\le m\) on \(S\cap F(S)\) and (6) on \(S\setminus F(S)\) to obtain \[\begin{align*} \lvert U\rvert-2\lvert F_G(U)\rvert+\lvert F_G^2(U)\rvert &\le m\bigl(\lvert H_0\rvert-2\lvert F(S)\rvert +\lvert S\cap F(S)\rvert\bigr) +\lvert S\setminus F(S)\rvert\\ &\le m\bigl(\lvert F^2(S)\setminus F(S)\rvert -\lvert F(S)\setminus S\rvert\bigr)+n. \end{align*}\] If \(S\subsetneq V(D)\), the parenthesized difference is an integer strictly less than zero by (3). The last bound is consequently at most \(-m+n<0\).

It remains to consider \(S=V(D)\), for which the subset-deficit hypothesis does not apply. Positive indegrees in \(D\) give \(F(S)=V(D)\), so \(F_G(U)=V(G)\). Positive indegrees in \(G\) then give \(F_G^2(U)=V(G)\) as well. In this case \[\lvert U\rvert-2\lvert F_G(U)\rvert+\lvert F_G^2(U)\rvert =\lvert U\rvert-\lvert V(G)\rvert<0,\] because \(U\) is proper. This proves the required inequality for every allowed \(U\). ◻

Proof of Proposition 2. Choose a counterexample of minimum order and then minimum number of arcs. Lemma 3 supplies positive indegrees and the subset deficit, so Lemma 4, with any integer \(m>\lvert V(D)\rvert\), supplies the required graph \(G\). ◻

Proof. Suppose instead that \(x_jy_s\ne0\). For a nonzero real \(\tau\), the matrix \(D_\tau=D+\tau e_s e_j^{\mathsf T}\) is still supported on \(T\), and \[D_\tau x=\tau x_j e_s.\] Thus \(e_s\in\mathop{\mathrm{im}}D_\tau\). Moreover, for every \(w\in\mathbb R^J\), \[Dw=D_\tau w-\tau w_j e_s\in\mathop{\mathrm{im}}D_\tau,\] so the entire old image \(\mathop{\mathrm{im}}D\) is contained in \(\mathop{\mathrm{im}}D_\tau\). On the other hand, \(y\) annihilates \(\mathop{\mathrm{im}}D\) and \(y_s\ne0\), so \(e_s\notin\mathop{\mathrm{im}}D\). Therefore \(\mathop{\mathrm{rank}}D_\tau>\mathop{\mathrm{rank}}D\), a contradiction. ◻

Proof of Lemma 5. If there are no conflicts, retain every member; then \(Z=H=\varnothing\) and the assertion is immediate. In what follows, all vector spaces have their usual coordinate bases. Empty minors have determinant \(1\), so the rank arguments also apply when a matching or an index set is empty.

The augmented graph and the required matching bound. Form a bipartite graph \(\Gamma\) with parts \[\mathcal V_L=\mathcal R\sqcup Z_L, \qquad \mathcal V_R=\mathcal C\sqcup Z_R,\] where \(Z_L\) and \(Z_R\) are separate copies of \(Z\), disjoint also from the two original families. Join conflicting original members. Also join each original member to the opposite copy of every point of \(Z\) that it covers. There are no edges between \(Z_L\) and \(Z_R\). Figure 1 displays the three edges forced by one conflict.

An initially conflict-free member is isolated in \(\Gamma\). Indeed, if \((p,j)\in\mathcal R\) covered \((i,j)\in Z\), an original conflict witnessing \((i,j)\in Z\) would supply a member \((i,s)\in\mathcal C\) with \(s\to j\). This member would conflict with \((p,j)\). The same argument with the sides exchanged applies to \(\mathcal C\).

It suffices to find a vertex cover \(K\) of \(\Gamma\) of size at most \(\lvert Z\rvert+\lvert H\rvert\), omitting isolated vertices. Delete precisely its original members. No conflict then survives. If \(q\) points of \(Z\) are uncovered by the surviving members, each of the other \(\lvert Z\rvert-q\) points has a surviving member adjacent to one of its two copies. That copy must lie in \(K\). Distinct points require distinct new vertices, whence \[ \lvert K\cap(\mathcal R\sqcup\mathcal C)\rvert \leq \lvert K\rvert-(\lvert Z\rvert-q)\leq\lvert H\rvert+q. \tag{9}\] Thus the cover gives exactly (8) and retains every initially conflict-free member.

We will obtain this cover by proving that a maximum matching in \(\Gamma\) has size at most \(\lvert Z\rvert+\lvert H\rvert\) and then giving the usual alternating-path construction of the cover. Choose a maximum matching \(\mathcal M\) with the fewest edges between original members. Write \(k\) for the number of these edges, and let \(\alpha\) and \(\beta\) be its edges in \(\mathcal R\times Z_R\) and \(Z_L\times\mathcal C\), respectively. Put \[\ell=\lvert \alpha\rvert,\qquad t=\lvert \beta\rvert, \qquad\lvert \mathcal M\rvert=k+\ell+t.\]

Each of \(\alpha\) and \(\beta\) is a maximum matching in its own subgraph. For example, if the \(\mathcal R\)–\(Z_R\) subgraph had a larger matching, its symmetric difference with \(\alpha\) would contain an \(\alpha\)-augmenting path, starting at an \(\alpha\)-unmatched member of \(\mathcal R\) and ending at an \(\alpha\)-unmatched vertex of \(Z_R\). The latter vertex is unmatched in \(\mathcal M\), and every internal vertex of the path is matched by \(\alpha\). If the starting member is unmatched in \(\mathcal M\), augmenting gives a larger matching in \(\Gamma\). Otherwise it lies on an original–original edge of \(\mathcal M\); remove that edge and augment along the path. This preserves the total size and reduces \(k\). Both conclusions contradict the choice of \(\mathcal M\). The proof for \(\beta\) is identical with the sides exchanged. Denote by \(R_\alpha\subseteq\mathcal R\) and \(C_\beta\subseteq\mathcal C\) the original vertices matched by these two matchings.

Four maps and a simultaneous choice of coefficients. To bound \(k+\ell+t\), we encode the two maximum matchings by matrix ranks. For each arrow \(x\to y\), introduce independent variables \(a_{xy}\) and \(b_{xy}\), with the two arrays independent of one another. Set both entries to zero when \(x\not\to y\). We shall choose real values for all the variables shortly. For any real assignment, define four maps by \[\begin{array}{ccc} \mathbb R^{\mathcal R}&\xrightarrow{\ L\ }&\mathbb R^Z\\[3pt] {\scriptstyle B}\big\downarrow&&\big\downarrow{\scriptstyle N}\\[3pt] \mathbb R^H&\xrightarrow{\ A\ }&\mathbb R^{\mathcal C} \end{array}\] with entries \[ \begin{aligned} L_{(i,j),(p,j)}&=a_{pi},& N_{(i,s),(i,j)}&=b_{sj},\\ B_{(p,s),(p,j)}&=b_{sj},& A_{(i,s),(p,s)}&=a_{pi}. \end{aligned} \tag{10}\] The row and column indices in each formula range over its indicated coordinate sets, and every entry not of a listed form is zero. The maps \(L,A\) change the first coordinate forward along \(p\to i\); \(N,B\) change the second coordinate backward from \(j\) to \(s\) along \(s\to j\). For a conflict, the two routes from \((p,j)\) to \((i,s)\) change the coordinates in opposite orders, through \((i,j)\in Z\) or \((p,s)\in H\). For a fixed column \((p,j)\in\mathcal R\) and row \((i,s)\in\mathcal C\), the only possible intermediate index in \(NL\) is \((i,j)\), and the only possible one in \(AB\) is \((p,s)\). If the two endpoints conflict, these indices belong to \(Z\) and \(H\), respectively, and both products have entry \(a_{pi}b_{sj}\). If they do not conflict, at least one factor is zero in both products. Hence \[ NL=AB. \tag{11}\]

We seek an assignment for which \[\mathop{\mathrm{rank}}L=\ell,\qquad \mathop{\mathrm{rank}}N=t,\qquad \dim\ker A\geq k.\] These three conditions give the desired matching bound. Indeed, rank–nullity and \(NL=AB\) would give \[\begin{align*} \lvert H\rvert &=\dim\ker A+\mathop{\mathrm{rank}}A\\ &\geq k+\mathop{\mathrm{rank}}A \geq k+\mathop{\mathrm{rank}}(NL)\\ &\geq k+\ell+t-\lvert Z\rvert. \tag{12}\end{align*}\] The last inequality follows by restricting \(N\) to \(\mathop{\mathrm{im}}L\): \[\mathop{\mathrm{rank}}(NL) =\dim\mathop{\mathrm{im}}L-\dim(\mathop{\mathrm{im}}L\cap\ker N) \geq\ell-(\lvert Z\rvert-t).\] The first two rank conditions will come from \(\alpha\) and \(\beta\). For the third, we will lift the \(k\) original left endpoints to vectors \(u^r\in\ker L\) and show that their images \(Bu^r\) are independent. The identity \(AB=NL\) places these images in \(\ker A\).

Our choice of coefficients uses the correspondence between generic matrix rank and maximum matching size (Edmonds 1967, sec. 5, Theorem 1). We apply the determinant argument within coordinate blocks and verify that all required minors can be nonzero at the same assignment. We choose the coefficients so that \(\mathop{\mathrm{rank}}L=\ell\), with its \(R_\alpha\) columns a basis of \(\mathop{\mathrm{im}}L\), and \(\mathop{\mathrm{rank}}N^{\mathsf T}=t\), with its \(C_\beta\) columns a basis of \(\mathop{\mathrm{im}}N^{\mathsf T}\). To justify this choice, a nonzero minor of \(L\) requires a matching between its column and row indices: a nonzero term in its determinant supplies the matching. Since \(\alpha\) is maximum, \(\mathop{\mathrm{rank}}L\leq\ell\) for every coefficient assignment. The square minor using precisely the endpoints of \(\alpha\) is, up to row and column ordering, block diagonal by the second coordinate \(j\). In each block all allowed entries are distinct variables \(a_{pi}\). The matching gives a determinant monomial that cannot cancel, because different permutations use different sets of these variables. Each block determinant is therefore a nonzero polynomial, and so is their product. Variables may occur in more than one block, but a product of nonzero polynomials remains nonzero. This proves the required independence when that minor does not vanish. For \(N^{\mathsf T}\) the same argument uses blocks with the first coordinate \(i\) fixed and distinct variables \(b_{sj}\) within each block.

One additional finite collection of rank conditions will be needed. For every arrow \(p\to i\), define \[J_p=\{j:(p,j)\in\mathcal R\},\qquad S_i=\{s:(i,s)\in\mathcal C\},\qquad D^{p,i}=(b_{sj})_{s\in S_i,\ j\in J_p}.\] We require \(D^{p,i}\) to have maximum rank among all matrices supported on \[T^{p,i}=\{(s,j)\in S_i\times J_p:s\to j\}.\] These matrices will let Lemma 6 compare restrictions of vectors in \(\ker B\) and \(\ker N^{\mathsf T}\). The allowed entries of each individual \(D^{p,i}\) are independent variables. A minor attaining its maximum possible rank at some assignment is therefore a nonzero polynomial in the \(b\) variables. Choose one such minor for each arrow, taking the empty minor when the maximum rank is zero. Multiply these finitely many polynomials with the two matching minors just described. The product is nonzero in the polynomial ring generated by all \(a\) and \(b\) variables, even though variables are shared between different matrices. A nonzero real polynomial is nonzero at some real assignment, as follows by induction on its number of variables. Fix such an assignment once and for all. It gives these support ranks and the two basis properties simultaneously.

For every edge \((r,c)\) of \(\mathcal M\) between original members, the basis properties now give vectors \[ \begin{aligned} u^r&=e_r+\sum_{a\in R_\alpha}\lambda_a^r e_a \in\ker L,\\ v^c&=e_c+\sum_{b\in C_\beta}\mu_b^c e_b \in\ker N^{\mathsf T}. \end{aligned} \tag{13}\] The original–original endpoints are disjoint from \(R_\alpha\) and \(C_\beta\), respectively. In particular, the \(u^r\) restrict to distinct unit vectors on the \(k\) original left endpoints, and \(v^c_c=1\).

The kernel restriction and the matching bound. It remains to show that the \(k\) lifts just constructed give independent vectors \(Bu^r\). The key assertion, at our fixed coefficient assignment, is \[ u_{pj}v_{is}=0 \quad\text{for every conflict }((p,j),(i,s)), \quad u\in\ker B,\quad v\in\ker N^{\mathsf T}. \tag{14}\] Here the assertion quantifies over all vectors in the two kernels.

To prove it, fix an arrow \(p\to i\). For \(u\in\ker B\), consider the vector \((u_{pj})_{j\in J_p}\). If a row \(s\in S_i\) of \(D^{p,i}\) has an allowed entry, choose \(j\in J_p\) with \(s\to j\). Then \((p,j)\) and \((i,s)\) conflict, so \((p,s)\in H\). The complete equation of \(Bu=0\) at this coordinate is \[ \sum_{j\in J_p}b_{sj}u_{pj}=0. \tag{15}\] If the row has no allowed entry, this equation holds because all its coefficients are zero. Thus it holds for every \(s\in S_i\), including rows for which \((p,s)\) is absent from \(H\). Consequently \((u_{pj})_{j\in J_p}\in\ker D^{p,i}\).

Similarly, let \(v\in\ker N^{\mathsf T}\). If a column \(j\in J_p\) of \(D^{p,i}\) has an allowed entry, choose \(s\in S_i\) with \(s\to j\). The resulting conflict implies \((i,j)\in Z\), and the complete equation of \(N^{\mathsf T}v=0\) at this coordinate is \[ \sum_{s\in S_i}b_{sj}v_{is}=0. \tag{16}\] Columns with no allowed entries satisfy the same equation automatically. Hence \((v_{is})_{s\in S_i}\in\ker(D^{p,i})^{\mathsf T}\). Since \(D^{p,i}\) has maximum rank on its allowed support, Lemma 6 gives \(u_{pj}v_{is}=0\) whenever \(s\to j\), proving (14). The hypothetical single-entry perturbation in that lemma concerns only \(D^{p,i}\); it need not preserve any other rank condition. The conclusion holds for every pair of kernel vectors at the fixed, original assignment.

For each original–original matched edge \((r,c)\), substitute \(v=v^c\) in (14). Since \(v^c_c=1\), every vector in \(\ker B\) vanishes at \(r\). It follows that the vectors \(Bu^r\), as \(r\) ranges over the \(k\) original left endpoints, are linearly independent. Indeed, a relation \[\sum_r\theta_r Bu^r=0\] puts the single vector \(u=\sum_r\theta_r u^r\) in \(\ker B\). Its coordinate at each such endpoint \(r\) is \(u_r=\theta_r\), by (13). All these coordinates vanish, so every \(\theta_r\) is zero. Furthermore, \[A(Bu^r)=NLu^r=0\] by (11). Thus \(\dim\ker A\geq k\), establishing the third rank condition. Equation (12) now gives \(\lvert \mathcal M\rvert=k+\ell+t\leq\lvert Z\rvert+\lvert H\rvert\), as required.

From the matching bound to a pruning. For completeness, we give the matching-to-cover argument in Kőnig’s theorem (Kőnig 1931). Starting at all unmatched vertices of \(\mathcal V_L\), follow edges outside \(\mathcal M\) from left to right and edges in \(\mathcal M\) from right to left. Let \(W_L,W_R\) be the reached vertices on the two sides. No unmatched right vertex is reached, since an alternating path to one would augment the maximum matching. The endpoints of a matched edge are either both reached or both unreached: a reached right endpoint leads to its mate, and a matched left endpoint can only have been reached through its mate. It follows that \[K=(\mathcal V_L\setminus W_L)\cup W_R\] covers every edge. Indeed, an edge from a reached left vertex to an unreached right vertex could be neither an unmatched edge, which would be traversed, nor a matched edge, whose endpoints have the same reachability. The cover contains exactly one endpoint of each matched edge and no unmatched vertices. Hence \(\lvert K\rvert=\lvert \mathcal M\rvert\leq\lvert Z\rvert+\lvert H\rvert\); it also omits isolated vertices. Applying (9) to this \(K\) proves the lemma. ◻

Proof. Suppose that such a graph exists, and put \(X=V(G)\). For \(S\subseteq X\times X\), define the two coordinate image operators by \[\begin{aligned} F_1S&=\{(i,j): (p,j)\in S\text{ and }p\to i \text{ for some }p\in X\},\\ F_2S&=\{(i,j): (i,s)\in S\text{ and }s\to j \text{ for some }s\in X\}. \end{aligned}\] Write \(F_1^2=F_1\circ F_1\), \(F_2^2=F_2\circ F_2\), and \(\Delta=\{(v,v):v\in X\}\). Call \(P,Q\subseteq X\times X\) compatible if \(F_1P\cap F_2Q=\varnothing\). Equivalently, no left member \((p,j)\in P\) and right member \((i,s)\in Q\) satisfy both \(p\to i\) and \(s\to j\); this is precisely the conflict relation in Lemma 5.

The pair \(P=Q=\Delta\) is compatible: a point \((i,j)\) in both images would require \(j\to i\) and \(i\to j\), contrary to orientation. Thus we may choose, among all compatible pairs with \(\Delta\subseteq P\cap Q\), one maximizing \(M+d\), where \[M=\lvert P\rvert+\lvert Q\rvert,\qquad d=\lvert X\rvert^2-\lvert F_1P\rvert-\lvert F_2Q\rvert.\] Such a maximum exists because \(X\) is finite. Compatibility makes \(d\) the number of points outside \(F_1P\cup F_2Q\). Including these uncovered points in the objective lets the points left uncovered by pruning offset the corresponding part of the deletion cost.

Every column \(P_j=\{p:(p,j)\in P\}\) is nonempty, since \(j\in P_j\). It is also proper. Indeed, positive indegrees give \(F(X)=X\), so \(P_j=X\) would imply \(X\times\{j\}\subseteq F_1P\). Choose an in-neighbor \(w\) of \(j\). Then \((w,j)\in F_2\Delta\subseteq F_2Q\), contradicting compatibility. Likewise every row \(Q_i=\{s:(i,s)\in Q\}\) contains \(i\). If \(Q_i=X\), then \(\{i\}\times X\subseteq F_2Q\); choosing \(w\to i\) gives \((i,w)\in F_1\Delta\subseteq F_1P\), again a contradiction. We can therefore sum (17) over the columns of \(P\) and over the rows of \(Q\) to obtain \[ \lvert P\rvert+\lvert F_1^2P\rvert<2\lvert F_1P\rvert,\qquad \lvert Q\rvert+\lvert F_2^2Q\rvert<2\lvert F_2Q\rvert. \tag{18}\]

Define new left and right families by taking complements in \(X\times X\): \[\mathcal R=(X\times X)\setminus F_2^2Q, \qquad \mathcal C=(X\times X)\setminus F_1^2P.\] The two strict inequalities in (18) give \[ \begin{aligned} \lvert \mathcal R\rvert+\lvert \mathcal C\rvert &=2\lvert X\rvert^2-\lvert F_2^2Q\rvert-\lvert F_1^2P\rvert\\ &>2\lvert X\rvert^2+M-2\bigl(\lvert F_1P\rvert+\lvert F_2Q\rvert\bigr) =M+2d. \end{aligned} \tag{19}\] These families need not be compatible. We will apply the pruning lemma, first verifying that the diagonal survives and then bounding the cost.

Both families contain \(\Delta\). If \((v,v)\in F_2^2Q\), there is an \(s\to v\) with \((v,s)\in F_2Q\). But \((s,s)\in P\) gives \((v,s)\in F_1P\), a contradiction. If \((v,v)\in F_1^2P\), there is a \(p\to v\) with \((p,v)\in F_1P\). Now \((p,p)\in Q\) gives \((p,v)\in F_2Q\), the same contradiction.

Moreover, each diagonal member is conflict-free in the new families. A conflict between the left member \((v,v)\) and a right member \((i,s)\in\mathcal C\) would give the path \(s\to v\to i\). Starting at \((s,s)\in P\) and expanding its first coordinate twice would then put \((i,s)\) in \(F_1^2P\), contrary to its membership in \(\mathcal C\). A conflict between a left member \((p,j)\in\mathcal R\) and the right member \((v,v)\) would give \(p\to v\to j\). Expanding the second coordinate of \((p,p)\in Q\) twice would put \((p,j)\) in \(F_2^2Q\), again a contradiction. The preservation clause of Lemma 5 thus applies to every diagonal member on both sides.

Let \(H,Z\subseteq X\times X\) be the sets associated with \(\mathcal R,\mathcal C\) in that lemma. Thus each conflict \[(p,j)\in\mathcal R,\quad (i,s)\in\mathcal C,\quad p\to i,\quad s\to j\] contributes \((p,s)\) to \(H\) and \((i,j)\) to \(Z\). We claim that \[ H\subseteq (X\times X)\setminus(F_1P\cup F_2Q), \qquad\text{and hence}\qquad \lvert H\rvert\le d. \tag{20}\] To see this, fix such a conflict. If \((p,s)\in F_1P\), choose \((u,s)\in P\) with \(u\to p\). The path \(u\to p\to i\) then puts \((i,s)\) in \(F_1^2P\), contrary to \((i,s)\in\mathcal C\). If \((p,s)\in F_2Q\), choose \((p,t)\in Q\) with \(t\to s\). The path \(t\to s\to j\) puts \((p,j)\) in \(F_2^2Q\), contrary to \((p,j)\in\mathcal R\). This proves (20).

Apply Lemma 5 to obtain conflict-free families \(P'\subseteq\mathcal R\) and \(Q'\subseteq\mathcal C\). They still contain \(\Delta\), and their lack of conflicts means \(F_1P'\cap F_2Q'=\varnothing\). Set \[d'=\lvert X\rvert^2-\lvert F_1P'\rvert-\lvert F_2Q'\rvert.\] A point is covered by a kept left member exactly when it belongs to \(F_1P'\), and by a kept right member exactly when it belongs to \(F_2Q'\). Consequently at most \(d'\) points of \(Z\) are uncovered after pruning. By Lemma 5 and (20), at most \(d+d'\) members were deleted, counting the two sides separately. Using (19), we conclude that \[\begin{aligned} \lvert P'\rvert+\lvert Q'\rvert+d' &\ge \lvert \mathcal R\rvert+\lvert \mathcal C\rvert-(d+d')+d'\\ &>M+2d-(d+d')+d'=M+d. \end{aligned}\] This contradicts the choice of \(P,Q\) and proves the proposition. ◻

Proof of Theorem 1. If the theorem were false, Proposition 2 would produce a nonempty finite oriented graph with positive indegrees satisfying (17) for every nonempty proper vertex set. Proposition 7 rules out such a graph. ◻

Proof. Seacrest’s Proposition 2 proves that his arc-weighted Conjecture 4 is equivalent to the unweighted conjecture, so Theorem 1 gives (iii).

To obtain (i), set \(w(us)=\eta(s)\) on every arc. For each \(v,s\), \[\beta_v^w(s)= \begin{cases} \eta(s),&s\in N_2^+(v),\\ 0,&s\notin N_2^+(v). \end{cases}\] Indeed, when \(v\to s\), every eligible difference \(w(us)-w(vs)\) is zero. At an exact second out-neighbor, \(w(vs)=0\) and the maximum is \(\eta(s)\); no other endpoint contributes. Thus the two sides of (iii) become \(\eta(N_2^+(v))\) and \(\eta(N_1^+(v))\). This is the specialization noted immediately after Seacrest’s Proposition 2.

For (ii), let \(M_D\) have entry \(1\) at \((v,s)\) when \(s\in N_2^+(v)\), entry \(-1\) when \(s\in N_1^+(v)\), and zero otherwise. Reversing all arcs transposes this matrix: \(M_{\overleftarrow D}=M_D^{\mathsf T}\). Seacrest’s Theorem 1 applies Farkas’ lemma to give either a nonzero \(\eta\ge0\) with \(M_D\eta\ge0\), or a \(\xi\ge0\) with \(M_D^{\mathsf T}\xi<0\) at every coordinate. The latter contradicts (i) on \(\overleftarrow D\). Normalize the former weighting to total weight one, proving (ii). ◻

Proof. Suppose that \(D\) has no directed \(3\)-cycle. If \(w\in N_2^+(v)\), choose a path \(v\to u\to w\). The exact-distance definition excludes \(w=v\) and \(w\in N_1^+(v)\). If \(w\in N_1^-(v)\), the arc \(w\to v\) would close a directed \(3\)-cycle. Thus \(N_2^+(v)\subseteq Z(v)\) for every \(v\). Theorem 1 now gives a vertex with \[d^+(v)\leq\lvert N_2^+(v)\rvert\leq\lvert Z(v)\rvert.\] Since \(D\) is oriented, its first in- and out-neighborhoods are disjoint, and their cardinalities are the corresponding degrees. Hence \[n-1=d^+(v)+d^-(v)+\lvert Z(v)\rvert \geq 2d^+(v)+d^-(v),\] proving (i).

Under the hypotheses of (ii), absence of a directed \(3\)-cycle would therefore give \[n-1\geq2\delta^+(D)+\delta^-(D)\geq n,\] a contradiction. The integer degree thresholds are \(\delta^\pm(D)\geq\lceil n/3\rceil\), so this includes the endpoint when \(3\) divides \(n\). Finally, directed girth four excludes directed \(3\)-cycles; in the regular case the count in (i) becomes \(n-1\geq3r\), proving (iii). ◻