Sách The edge-count criterion for graphic lists

Abstract
We give a new short proof of Koren’s characterization of graphic lists, extended
to multigraphs with bounded multiplicity p, called p-graphs. The Edge-Count Cri-
terion (ECC) for an integer n-tuple d and integer p is the statement that for all
disjoint sets I and J of indices,
P
i∈I
di +
P
j∈J
[p(n ư 1) ư dj
] > p|I| |J|. An integer
list d is the degree list of a p-graph if and only if it has even sum and satisfies ECC.
Analogous statements hold for bipartite or directed graphs, and an old character-
ization of degree lists of signed graphs follows as a corollary of the extension to
multigraphs.