Secuencia de grados

Teorema de Erdős-Gallai

La secuencia de enteros ${\displaystyle d_{i}\,}$ con ${\displaystyle i=1,...,n-1\,}$ es una secuencia de grados de un grafo simple, si y sólo si:

• La suma de los enteros de la secuencia es par, y
• ${\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)}$

Teorema de Havel-Hakimi

Una secuencia de enteros ${\displaystyle d_{1}\geq d_{2}\geq ...\geq d_{v}\geq 0}$ es gráfica sí, y sólo sí también lo es la lista: ${\displaystyle d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{v}}$, que resulta de eliminar el primer elemento y restar una unidad a los siguientes ${\displaystyle d_{1}}$ valores de la lista.

Teorema de Hakimi

Una secuencia de enteros ${\displaystyle d_{1}\geq d_{2}\geq ...\geq d_{n}}$ donde ${\displaystyle n\geq 2}$ es multigráfica (o pseudográfica) sí, y sólo sí la suma ${\displaystyle \sum _{i=1}^{k}d_{i}}$ es par y ${\displaystyle d_{1}\leq d_{2}+...+d_{n}}$.