A remark on degree sequences of multigraphs

A sequence {d <Subscript>1</Subscript>, d <Subscript>2</Subscript>, . . . , d <Subscript> n </Subscript>} of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v <Subscript>1</Subscript>, v <Subscript>2</Subscript>, . . . , v <Subscript> n </Subscript> such that the degree d(v <Subscript> i </Subscript>) of the vertex v <Subscript> i </Subscript> equals d <Subscript> i </Subscript> for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow. Copyright Springer-Verlag 2009