定理1(Erd?s–Gallai theorem)：令\(n\)个点的度数序列降序后为\(\{d\}\)，\(n\)个点能形成图当且仅当：\(\sum d_i~is~even\)，\(\forall k\in[1,n],\sum\limits_{i=1}^k d_i\le (k-1)k+\sum\limits_{i=k+1}^n min(k,d_i)\)
证明：
右部分是上界，则任何图都满足
若满足数列，从前往后枚举每个点，向后向能连边的点连边
定理2(有向图)：令\(n\)个点按出度降序排列，出度与入度分别为\(\{a\},\{b\}\)，\(n\)个点能形成有向图当且仅当：\(\forall k\in[1,n]\sum\limits_{i=1}^k a_i\le \sum\limits_{i=1}^k min(b_i,k-1)+\sum\limits_{i=k+1}^n min(b_i,k)\)
原文：https://www.cnblogs.com/Grice/p/12894688.html