Graph density

In graph theory, the density ^[1] of a graph is the ratio of its number of edges to the maximum possible number of edges on its vertex set.

Definition

---

Definition 1 (Density of an undirected graph)

Let $G=(V,E)$ be a simple undirected graph with $n=|V|$ and $m=|E|$. The density of $G$ is

$$D(G):=\frac{m}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}=\frac{2m}{n(n-1)}$$

Definition 2 (Density of a directed graph)

Let $G=(V,E)$ be a directed graph with $n=|V|$ and $m=|E|$. Each ordered pair of distinct vertices admits at most one directed edge, so the maximum possible number of edges is $n(n-1)$, and the density of $G$ is

$$D(G):=\frac{m}{2\left(\genfrac{}{}{0ex}{}{n}{2}\right)}=\frac{m}{n(n-1)}$$

Notation

---

The density of $G$ is denoted $D(G)$.

Properties

---

The density of $G$ satisfies $0\le D(G)\le 1$, with $D(G)=0$ for a graph with no edges and $D(G)=1$ for the complete graph. Graphs with density close to $1$ are called dense, and those with density close to $0$ are called sparse.

References

1. [1]

   “Dense graph”, Wikipedia, Available: https://en.wikipedia.org/wiki/Dense_graph, Accessed: 2026-07-31 ↩