Mathwords logoMathwords

Graph Density — Definition, Formula & Examples

Graph density is a ratio that measures how many edges a graph has compared to the maximum number of edges it could have. A density of 0 means no edges, and a density of 1 means every possible edge is present (a complete graph).

For a simple undirected graph GG with nn vertices and mm edges, the density is defined as D(G)=2mn(n−1)D(G) = \frac{2m}{n(n-1)}, where n(n−1)/2n(n-1)/2 is the number of edges in the complete graph KnK_n. For a simple directed graph, the density is D(G)=mn(n−1)D(G) = \frac{m}{n(n-1)}, since each pair of vertices can have two directed edges.

Key Formula

D(G)=2mn(n−1)D(G) = \frac{2m}{n(n-1)}
Where:
  • D(G)D(G) = Density of the undirected simple graph G
  • mm = Number of edges in the graph
  • nn = Number of vertices in the graph

How It Works

To compute graph density, count the number of edges mm and the number of vertices nn in your graph. Plug these into the formula. The result is always between 0 and 1 inclusive. Graphs with density close to 1 are called dense graphs, while those with density close to 0 (or where mm grows much slower than n2n^2) are called sparse graphs. This distinction matters because many graph algorithms have different performance characteristics on dense versus sparse graphs.

Worked Example

Problem: Find the density of an undirected simple graph with 5 vertices and 7 edges.
Maximum edges: A complete graph on 5 vertices has:
n(n−1)2=5⋅42=10 edges\frac{n(n-1)}{2} = \frac{5 \cdot 4}{2} = 10 \text{ edges}
Apply the formula: Substitute m=7m = 7 and n=5n = 5 into the density formula:
D(G)=2⋅75⋅4=1420=0.7D(G) = \frac{2 \cdot 7}{5 \cdot 4} = \frac{14}{20} = 0.7
Answer: The graph density is 0.70.7, meaning 70% of all possible edges are present. This graph is relatively dense.

Why It Matters

Choosing between an adjacency matrix and an adjacency list often depends on graph density — matrices suit dense graphs, while lists are more memory-efficient for sparse ones. Network scientists use density to characterize real-world networks; for instance, social networks tend to be sparse despite having millions of nodes.

Common Mistakes

Mistake: Forgetting the factor of 2 in the numerator (or equivalently, not dividing the denominator by 2).
Correction: The formula D=2m/[n(n−1)]D = 2m / [n(n-1)] accounts for the fact that n(n−1)n(n-1) counts ordered pairs, while each undirected edge corresponds to one unordered pair. Make sure numerator and denominator are consistent.