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 (1960) proved that a degree sequence
is graphic iff the sum of vertex degrees is even and the
sequence obeys the property
for each integer
(Skiena 1990, p. 157), and this condition also generalizes to directed
graphs. Tripathi and Vijay (2003) showed that this inequality need be checked
only for as many
as there are distinct terms in the sequence, not for all .
Havel (1955) and Hakimi (1962) proved another characterization of graphic sequences, namely that a degree sequence with and is graphical iff the sequence
is graphical. In addition, Havel (1955) and Hakimi (1962) showed that if a degree
sequence is graphic, then there exists a graph such that the node of highest degree
is adjacent to the
next highest degree vertices of , where is the maximum
vertex degree of .
No degree sequence can be graphic if all the degrees occur with multiplicity 1 (Behzad and Chartrand 1967, p. 158; Skiena 1990, p. 158). Any degree sequence whose
sum is even can be realized by a multigraph
having loops (Hakimi 1962; Skiena 1990, p. 158).
Behzad, M. and Chartrand, G. "No Graph is Perfect." Amer. Math. Monthly74, 962-963, 1967.Eggleton, R. B.
"Graphic Sequences and Graphic Polynomials." In Infinite
and Finite Sets (Ed. A. Hajnal). Amsterdam, Netherlands: North-Holland,
pp. 385-293, 1975.Erdős, P. and Gallai, T. "Graphs with
Prescribed Degrees of Vertices" [Hungarian]. Mat. Lapok.11, 264-274,
1960.Fulkerson, D. R. "Upsets in Round Robin Tournaments."
Canad. J. Math.17, 957-969, 1965.Fulkerson, D. R.;
Hoffman, A. J.; and McAndrew, M. H. "Some Properties of Graphs with
Multiple Edges." Canad. J. Math.17, 166-177, 1965.Hakimi,
S. "On the Realizability of a Set of Integers as Degrees of the Vertices of
a Graph." SIAM J. Appl. Math.10, 496-506, 1962.Havel,
V. "A Remark on the Existence of Finite Graphs" [Czech]. Časopis
Pest. Mat.80, 477-480, 1955.Ryser, H. J. "Combinatorial
Properties of Matrices of Zeros and Ones." Canad. J. Math.9,
371-377, 1957.Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, p. 157, 1990.Tripathi, A. and Vijay, S. "A
Note on a Theorem of Erdős & Gallai." Discr. Math.265,
417-420, 2003.
is graphic iff the sum of vertex degrees is even and the
sequence obeys the property
(Skiena 1990, p. 157), and this condition also generalizes to directed
graphs. Tripathi and Vijay (2003) showed that this inequality need be checked
only for as many 
as there are distinct terms in the sequence, not for all 
.
and 
is graphical iff the sequence
is graphical. In addition, Havel (1955) and Hakimi (1962) showed that if a degree
sequence is graphic, then there exists a graph 
such that the node of highest degree
is adjacent to the 
next highest degree vertices of 
, where 
is the maximum
vertex degree of 
.
