En realidad, todo se reduce a lo que uno define como densidad. En la práctica, es simplemente la abreviatura de la fracción de aristas en un gráfico al máximo caso posible. Sea $f(n)$ sea el número máximo de aristas posibles en un gráfico $G$ con $n$ nodos, entonces la "densidad" de $G$ se definiría típicamente como:
$$\frac{|E|}{f(|V|)}$$
Hay $\binom{n}{m}$ posible $m$ -en un gráfico con $n$ nodos. Así, en el caso no dirigido, la densidad de $G$ con $n$ nodos es:
$$\frac{|E|}{\sum_{k=2}^n \binom{n}{k}}$$
Si estos se dirigen $m$ -cada arista puede ir a cualquiera de los $m$ vértices entre los que se encuentra. Para una arista 2, hay 2 orientaciones, etc. Con esto obtenemos
$$\frac{|E|}{\sum_{k=2}^n k \cdot \binom{n}{k}}$$
Pero realmente, esto es sólo una fracción. La densidad no es una propiedad gráfica especialmente valiosa, sólo es una notación conveniente.
Si se permiten múltiples aristas, hay un número infinito de aristas posibles para el gráfico, a menos que se tenga un número máximo de veces que una arista determinada puede repetirse. Si cada arista puede tener hasta $x$ copias, hay $x$ veces más bordes posibles. Es sólo una cuestión de simple combinatoria basada en cualquier restricción que pongas en $G$ ...
