Dense graph

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

Definition

---

Definition 1 (Dense graph)

Let $G$ be a graph. $G$ is a dense graph if its number of edges is close to 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 ↩