A graphic sequence is a sequence of numbers which can be the degree sequence of some graph. A sequence can be checked to determine if it is graphic using GraphicQ[g] in the Wolfram Language package Combinatoricaˋ . Erdős and Gallai proved that a degree sequence {d_1, ..., d_n} is graphic iff the sum of vertex degrees is even and the sequence obeys the property sum_(i = 1)^r d_i<=r(r - 1) + sum_(i = r + 1)^n min(r, d_i) for each integer r<=n - 1, and this condition also generalizes to directed graphs. Tripathi and Vijay showed that this inequality need be checked only for as many r as there are distinct terms in the sequence, not for all 1<=r<=n - 1.

degree sequence | graphical partition | vertex degree