A Characterization of the Degree Sequence of the Graph with Cyclomatic Number $k$

Abstract

Let $(d_1,d_2,\dots ,d_n)$ be a sequence of positive integers with $n-1\ge d_1\ge d_2\ge \cdots \ge d_n$. We give a characterization of $(d_1,d_2,\dots ,d_n)$ that is the degree sequence of a graph with cyclomatic number $k$. This simplifies the characterization of Erdős-Gallai.