 TOPICS # Graphic Sequence

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).

Degree Sequence, Graphical Partition, Vertex Degree

## Explore with Wolfram|Alpha More things to try:

## References

Behzad, M. and Chartrand, G. "No Graph is Perfect." Amer. Math. Monthly 74, 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.

Graphic Sequence

## Cite this as:

Weisstein, Eric W. "Graphic Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphicSequence.html