Exact vs Asymptotic Edge Density in Undirected Graphs
Exact Formula:
m = p × n(n-1)/2
Asymptotic Formula (large n):
m ≈ p × n²/2
For p = 0.5:
m ≈ n²/4
The asymptotic approximation becomes more accurate as n increases
Exact Formula
Asymptotic Formula
Comparison Table
n (nodes)
4
6
8
10
20
50
100
Exact m
3
8
14
23
95
613
2475
Asymptotic m
4
9
16
25
100
625
2500
Relative Error
33.3%
12.5%
14.3%
8.7%
5.3%
2.0%
1.0%
Show Exact Edge Counts
Show Asymptotic Edge Counts
Show Both