TheFulkerson–Chen–Anstee theorem is a result ingraph theory, a branch ofcombinatorics. It provides one of two known approaches solving thedigraph realization problem, i.e. it gives a necessary and sufficient condition for pairs of nonnegativeintegers${\displaystyle ((a_1,b_1),\dots ,(a_n,b_n))}$ to be theindegree-outdegree pairs of asimple directed graph; a sequence obeying these conditions is called "digraphic".D. R. Fulkerson^[1] (1960) obtained a characterization analogous to the classicalErdős–Gallai theorem for graphs, but in contrast to this solution with exponentially many inequalities. In 1966 Chen^[2] improved this result in demanding the additional constraint that the integer pairs must be sorted in non-increasinglexicographical order leading to n inequalities. Anstee^[3] (1982) observed in a different context that it is sufficient to have${\displaystyle a_1\ge \cdots \ge a_n}$. Berger^[4] reinvented this result and gives a direct proof.

A sequence${\displaystyle ((a_1,b_1),\dots ,(a_n,b_n))}$ of nonnegative integer pairs with${\displaystyle a_1\ge \cdots \ge a_n}$ is digraphic if and only if${\displaystyle \sum _{i=1}^n{a}_i=\sum _{i=1}^n{b}_i}$ and the following inequality holds fork such that${\displaystyle 1\le k\le n}$:

${\displaystyle \sum _{i=1}^k{a}_i\le \sum _{i=1}^{k}min(b_i,k-1)+\sum _{i=k+1}^{n}min(b_i,k)}$

Berger proved^[4] that it suffices to consider the${\displaystyle k}$th inequality such that with${\displaystyle a_k>a_{k+1}}$ and for${\displaystyle k=n}$.

The theorem can also be stated in terms of zero-onematrices. The connection can be seen if one realizes that eachdirected graph has anadjacency matrix where the column sums and row sums correspond to${\displaystyle (a_1,\dots ,a_n)}$ and${\displaystyle (b_1,\dots ,b_n)}$. Note that the diagonal of the matrix only contains zeros. There is a connection to the relationmajorization. We define a sequence${\displaystyle (a_1^{\ast },\dots ,a_n^{\ast })}$ with${\displaystyle a_k^{\ast }:=|\{b_i|i>k,b_i\ge k\}|+|\{b_i|i\le k,b_i\ge k-1\}|}$. Sequence${\displaystyle (a_1^{\ast },\dots ,a_n^{\ast })}$ can also be determined by acorrected Ferrers diagram. Consider sequences${\displaystyle (a_1,\dots ,a_n)}$,${\displaystyle (b_1,\dots ,b_n)}$ and${\displaystyle (a_1^{\ast },\dots ,a_n^{\ast })}$ as${\displaystyle n}$-dimensional vectors${\displaystyle a}$,${\displaystyle b}$ and${\displaystyle a^{\ast }}$. Since${\displaystyle \sum _{i=1}^k{a}_i^{\ast }=\sum _{i=1}^{k}min(b_i,k-1)+\sum _{i=k+1}^{n}min(b_i,k)}$ by applying the principle ofdouble counting, the theorem above states that a pair of nonnegative integer sequences${\displaystyle (a,b)}$ with nonincreasing${\displaystyle a}$ is digraphicif and only if vector${\displaystyle a^{\ast }}$ majorizes${\displaystyle a}$.

A sequence${\displaystyle ((a_1,b_1),\dots ,(a_n,b_n))}$ of nonnegative integer pairs with${\displaystyle a_1\ge \cdots \ge a_n}$ is digraphic if and only if${\displaystyle \sum _{i=1}^n{a}_i=\sum _{i=1}^n{b}_i}$ and there exists a sequence${\displaystyle c}$ such that the pair${\displaystyle (c,b)}$ is digraphic and${\displaystyle c}$ majorizes${\displaystyle a}$.^[5]

Similar theorems describe the degree sequences of simple graphs, simple directed graphs with loops, and simple bipartite graphs. The first problem is characterized by theErdős–Gallai theorem. The latter two cases, which are equivalent see Berger,^[4] are characterized by theGale–Ryser theorem.

• Kleitman–Wang algorithms

• Theorems in graph theory