zu einem Graphen G mit der Eckenmeng E(G) ={x₁, x₂,…,x_n} die Folge \begin{eqnarray}{d}_{G}({x}_{1}),\,{d}_{G}({x}_{2}),\ldots,{d}_{G}({x}_{n})\,.\end{eqnarray}

Eine Folge nicht negativer ganzer Zahlen d₁, d₂,…,d_n heißt graphisch, wenn ein Graph existiert, der diese Folge als Gradfolge besitzt. Es ergibt sich unmittelbar die interessante Frage, welche Folgen graphisch sind. Durch sukzessives Anwenden der folgenden notwendigen und hinreichenden Bedingung von V. Havel (1955) und S.L. Hakimi (1962) läßt sich leicht entscheiden, ob eine Folge graphisch ist.

Eine gegebene Folge nicht negativer ganzer Zahlen d₁ ≥ d₂ ≥…≥ d_n ist genau dann graphisch, wenn die Folge \begin{eqnarray}{d}_{1}\,-\,1,\ldots,{d}_{{d}_{n}}\,-\,1,\,{d}_{{d}_{n+1}},\ldots,{d}_{n-1}\end{eqnarray}graphisch ist.

Bei der praktischen Anwendung des Kriteriums von Havel und Hakimi sollte man allerdings zunächst testen, ob die gegebene Folge das Hand-schlaglemma erfüllt, also ob \(\displaystyle {\sum }_{i=1}^{n}{d}_{i}\) eine gerade Zahl ist.

Ein weitere wichtige Charakterisierung graphischer Folgen wurde 1960 von P. Erdős und T. Gallai präsentiert:

Eine gegebene Folge nicht negativer ganzer Zahlen d₁ ≥ d₂ ≥…≥ d_n ist genau dann graphisch, wenn \(\displaystyle {\sum }_{i=1}^{n}{d}_{i}\) gerade ist, und wenn \begin{eqnarray}\displaystyle \sum _{i=1}^{p}{d}_{i}\,\le \,p(p\,-\,1)\,+\,\displaystyle \sum _{i=p+1}^{n}\min \{p,{d}_{i}\}\end{eqnarray}für alle p mit 1 ≤ p ≤ n gilt.