Sparse graph

In graph theory, a sparse graph ^[1] is a graph whose number of edges is much smaller than the maximum number of edges possible on its vertex set. Its counterpart is a dense graph, one whose number of edges is close to that maximum.

Definition

---

Definition 1 (Sparse graph)

Let $G$ be a graph. $G$ is a sparse graph if its number of edges is much smaller than the maximum number of edges possible on its vertex set, as measured by its density.

References

1. [1]

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