A proof of Seymour’s second-neighborhood conjecture

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

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 \abs{N_{1,D_T}^+(v)}\le\abs{N_{2,D_T}^+(v)}. 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

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

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

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=\abs{N_{1,D}^+(v)} and d_2=\abs{N_{2,D}^+(v)}. The gains and losses just identified imply

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

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)<\abs{E}. Finally, F(S)=I\cup E and F(I)\subseteq F(S), so

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

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

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

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

Combining these estimates gives the sharper bound

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 (); it remains a valid upper bound. Now use \abs{T_v}\le m on S\cap F(S) and (6) on S\setminus F(S) to obtain

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

because U is proper. This proves the required inequality for every allowed U.□

Proof of Proposition 2.1. Choose a counterexample of minimum order and then minimum number of arcs. Lemma 2.2 supplies positive indegrees and the subset deficit, so Lemma 2.3, with any integer m>\abs{V(D)}, 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

Thus e_s\in\im D_\tau. Moreover, for every w\in\R^J,

so the entire old image \im D is contained in \im D_\tau. On the other hand, y annihilates \im D and y_s\ne0, so e_s\notin\im D. Therefore \rank D_\tau>\rank D, a contradiction.□

Proof of Lemma 3.1. 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

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 \abs Z+\abs H, 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 \abs Z-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

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 \abs Z+\abs H 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

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

with entries

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

We seek an assignment for which

These three conditions give the desired matching bound. Indeed, rank–nullity and NL=AB would give

The last inequality follows by restricting N to \im L:

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 [9, Section 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 \rank L=\ell, with its R_\alpha columns a basis of \im L, and \rank N^{\mathsf T}=t, with its C_\beta columns a basis of \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, \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

We require D^{p,i} to have maximum rank among all matrices supported on

These matrices will let Lemma 3.2 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

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

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

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

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 3.2 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

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,

by (11). Thus \dim\ker A\geq k, establishing the third rank condition. Equation (12) now gives \abs{\mathcal M}=k+\ell+t\leq\abs Z+\abs H, as required.

From the matching bound to a pruning. For completeness, we give the matching-to-cover argument in Kőnig’s theorem [17]. 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

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 \abs K=\abs{\mathcal M}\leq\abs Z+\abs H; 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

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 3.1.

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

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

Define new left and right families by taking complements in X\times X:

The two strict inequalities in (18) give

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 3.1 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

contributes (p,s) to H and (i,j) to Z. We claim that

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 3.1 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

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 3.1 and (20), at most d+d' members were deleted, counting the two sides separately. Using (19), we conclude that

This contradicts the choice of P,Q and proves the proposition.□

Proof of Theorem 1.1. If the theorem were false, Proposition 2.1 would produce a nonempty finite oriented graph with positive indegrees satisfying (17) for every nonempty proper vertex set. Proposition 4.1 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.1 gives (iii).

To obtain (i), set w(us)=\eta(s) on every arc. For each v,s,

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.1 now gives a vertex with

Since D is oriented, its first in- and out-neighborhoods are disjoint, and their cardinalities are the corresponding degrees. Hence

proving (i).

Under the hypotheses of (ii), absence of a directed 3-cycle would therefore give

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).□