The Gale–Ryser theorem is a result in graph theory and combinatorial matrix theory, two branches of combinatorics. It provides one of two known approaches to solving the bipartite realization problem, i.e. it gives a necessary and sufficient condition for two finite sequences of natural numbers to be the degree sequence of a labeled simple bipartite graph; a sequence obeying these conditions is called "bigraphic". It is an analog of the Erdős–Gallai theorem for simple graphs. The theorem was published independently in 1957 by H. J. Ryser and David Gale.
Statement A pair of sequences of nonnegative integers ( a 1 , … , a n ) {\displaystyle (a_{1},\ldots ,a_{n})} and ( b 1 , … , b m ) {\displaystyle (b_{1},\ldots ,b_{m})} with a 1 ≥ ⋯ ≥ a n {\displaystyle a_{1}\geq \cdots \geq a_{n}} is bigraphic if and only if ∑ i = 1 n a i = ∑ i = 1 m b i {\displaystyle \sum _{i=1}^{n}a_{i}=\sum _{i=1}^{m}b_{i}} and the following inequality holds for all k ∈ { 1 , … , n } {\displaystyle k\in \{1,\ldots ,n\}} :
∑ i = 1 k a i ≤ ∑ i = 1 m min ( b i , k ) . {\displaystyle \sum _{i=1}^{k}a_{i}\leq \sum _{i=1}^{m}\min(b_{i},k).}
Sometimes this theorem is stated with the additional constraint b 1 ≥ ⋯ ≥ b m {\displaystyle b_{1}\geq \cdots \geq b_{m}} . This condition is not necessary, because the labels of vertices of one partite set in a bipartite graph can be rearranged arbitrarily. In 1962 Ford and Fulkerson gave a different but equivalent formulation of the theorem.
… excerpt ends here. Continue reading the full article.
