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 Criterion (ECC) for an integer $n$-tuple $d$ and integer $p$ is the statement that for all disjoint sets $I$ and $J$ of indices, $\sum_{i\in I} d_i+\sum_{j\in J} [p(n-1)-d_j]\ge 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 characterization of degree lists of signed graphs follows as a corollary of the extension to multigraphs.