Chapter 54. Sparse and Dense Graphs
Chapter 54. Sparse and Dense Graphs
Graphs differ greatly in how many edges they contain.
Some graphs contain only enough edges to maintain limited connectivity. Others contain edges between almost every pair of vertices. This distinction leads to the concepts of sparse and dense graphs.
Sparsity and density influence nearly every aspect of graph theory: connectivity, expansion, algorithms, random graphs, matrix representations, storage complexity, and asymptotic behavior.
The number of edges is one of the most basic measurements of graph structure.
54.1 Number of Edges
Let
$$ G=(V,E) $$
be a simple undirected graph with
$$ |V|=n $$
vertices and
$$ |E|=m $$
edges.
Since every edge joins two distinct vertices, the maximum possible number of edges is
$$ \binom{n}{2} = \frac{n(n-1)}{2}. $$
This maximum occurs precisely for the complete graph
$$ K_n. $$
Thus every simple graph satisfies
$$ 0\le m\le \frac{n(n-1)}{2}. $$
The quantity (m) is the first indicator of sparsity or density.
54.2 Sparse Graphs
Informally, a sparse graph has relatively few edges compared with the number of vertices.
In asymptotic graph theory, a family of graphs is usually called sparse when
$$ m=O(n). $$
This means the number of edges grows at most linearly with the number of vertices.
Typical sparse graphs include:
| Graph | Number of edges |
|---|---|
| Tree | (n-1) |
| Path | (n-1) |
| Cycle | (n) |
| Bounded-degree graph | (O(n)) |
| Planar graph | (O(n)) |
Sparse graphs often have local structure, geometric constraints, or bounded degree.
Many real-world networks are sparse. Even very large social, communication, or biological networks usually contain far fewer than all possible edges.
54.3 Dense Graphs
A graph is dense when the number of edges is close to quadratic in the number of vertices.
A family of graphs is often called dense when
$$ m=\Theta(n^2). $$
This means the graph contains a constant fraction of all possible edges.
Examples include:
| Graph | Number of edges |
|---|---|
| Complete graph (K_n) | (\frac{n(n-1)}{2}) |
| Complete bipartite graph (K_{n,n}) | (n^2) |
| Random graph (G(n,p)) with constant (p) | Approximately (pn^2/2) |
Dense graphs tend to have strong global connectivity and many short paths.
In a dense graph, local neighborhoods overlap heavily. Distances are usually small, and separators are often large.
54.4 Average Degree
The average degree provides another way to measure sparsity.
Since every edge contributes (2) to the degree sum,
$$ \sum_{v\in V}\deg(v)=2m. $$
Therefore the average degree is
$$ \frac{1}{n}\sum_{v\in V}\deg(v) = \frac{2m}{n}. $$
This quantity is often denoted by
$$ \bar d. $$
A graph family is sparse precisely when the average degree remains bounded:
$$ \bar d=O(1). $$
Dense graphs have average degree growing linearly with (n).
For example:
| Graph | Average degree |
|---|---|
| Tree | Approximately (2) |
| Cycle | (2) |
| (d)-regular graph | (d) |
| Complete graph (K_n) | (n-1) |
Thus sparsity can be viewed either through edge count or through average degree.
54.5 Minimum and Maximum Degree
The degree sequence also reflects sparsity and density.
Let
$$ \delta(G) $$
denote the minimum degree, and let
$$ \Delta(G) $$
denote the maximum degree.
If (\Delta(G)) is bounded independently of (n), then the graph is sparse because
$$ m\le \frac{n\Delta(G)}{2}. $$
Conversely, dense graphs typically have large average and maximum degree.
However, sparsity is global, not local. A graph may contain a few high-degree vertices and still be sparse overall.
For example, a star graph has one vertex of degree
$$ n-1, $$
yet it contains only
$$ n-1 $$
edges and is therefore sparse.
54.6 Trees as Minimal Connected Graphs
Trees are the sparsest connected graphs.
A connected graph with (n) vertices must contain at least
$$ n-1 $$
edges. Trees achieve this minimum exactly.
Thus:
| Property | Meaning |
|---|---|
| Connected graph | At least (n-1) edges |
| Tree | Exactly (n-1) edges |
| Sparse connected graph | Close to tree structure |
This explains why trees are fragile. Every edge is essential.
Adding more edges creates cycles and redundancy.
54.7 Complete Graphs as Maximally Dense Graphs
Complete graphs are the densest possible simple graphs.
The complete graph
$$ K_n $$
contains every possible edge:
$$ m=\frac{n(n-1)}{2}. $$
Every vertex has degree
$$ n-1. $$
Complete graphs maximize many graph parameters:
| Parameter | Value in (K_n) |
|---|---|
| Connectivity | (n-1) |
| Edge connectivity | (n-1) |
| Diameter | (1) |
| Chromatic number | (n) |
| Clique number | (n) |
Complete graphs therefore serve as the extreme dense case.
54.8 Planar Graphs Are Sparse
Planar graphs provide one of the most important sparse graph families.
Euler's formula implies that every simple planar graph with
$$ n\ge3 $$
satisfies
$$ m\le 3n-6. $$
Thus planar graphs have only linearly many edges.
In particular, planar graphs are sparse even when they contain many cycles and complicated structure.
This sparsity has major algorithmic consequences:
| Property | Consequence |
|---|---|
| Linear number of edges | Efficient storage |
| Small separators | Recursive decomposition |
| Bounded average degree | Local structure |
| Geometric constraints | Specialized algorithms |
Planarity therefore combines geometric structure with sparsity.
54.9 Random Graphs
Random graphs exhibit both sparse and dense regimes.
In the Erdős-Rényi model
$$ G(n,p), $$
each possible edge appears independently with probability (p).
The expected number of edges is
$$ \mathbb E[m] = p\binom{n}{2}. $$
If
$$ p=\frac{c}{n}, $$
for constant (c), then
$$ \mathbb E[m]=\Theta(n), $$
so the graph is sparse.
If (p) is a fixed positive constant, then
$$ \mathbb E[m]=\Theta(n^2), $$
so the graph is dense.
Thus changing (p) changes the structural regime of the graph.
54.10 Sparse Matrices and Graphs
Graphs and matrices are closely related.
The adjacency matrix of a graph with (n) vertices is an
$$ n\times n $$
matrix.
For sparse graphs, most entries are zero. The matrix is sparse.
For dense graphs, many entries are nonzero.
Sparse matrices are important because they allow specialized algorithms and storage methods.
| Matrix type | Graph type |
|---|---|
| Sparse matrix | Sparse graph |
| Dense matrix | Dense graph |
Many numerical methods depend critically on matrix sparsity.
Sparse linear systems appear in scientific computing, optimization, machine learning, and graph algorithms.
54.11 Algorithmic Differences
Sparse and dense graphs behave differently algorithmically.
Storage
A dense graph requires
$$ \Theta(n^2) $$
space if represented by an adjacency matrix.
A sparse graph can often be stored using adjacency lists with only
$$ \Theta(n+m) $$
space.
Traversal
Breadth-first search and depth-first search run in
$$ O(n+m) $$
time.
Thus they are nearly linear for sparse graphs but quadratic for dense graphs.
Matrix Algorithms
Dense graphs favor matrix-based methods because the matrices are already full.
Sparse graphs favor combinatorial methods because most entries are zero.
Shortest Paths
For sparse graphs, Dijkstra's algorithm with heaps is efficient.
For dense graphs, matrix-based approaches such as Floyd-Warshall may become competitive.
Thus graph density strongly affects algorithm design.
54.12 Extremal Graph Theory
Extremal graph theory studies how many edges a graph can have while avoiding certain subgraphs.
Typical questions include:
| Constraint | Maximum possible edges |
|---|---|
| No triangle | Turán's theorem |
| No cycle of given length | Extremal cycle theory |
| No complete bipartite subgraph | Zarankiewicz problem |
These problems lie between sparse and dense structure.
For example, a graph may be dense overall but forbidden from containing certain local configurations.
Extremal graph theory studies the tension between edge density and structural constraints.
54.13 Degeneracy
A graph is (k)-degenerate if every subgraph contains a vertex of degree at most (k).
Degeneracy measures a refined form of sparsity.
Examples:
| Graph family | Degeneracy |
|---|---|
| Forests | (1) |
| Outerplanar graphs | (2) |
| Planar graphs | At most (5) |
Bounded degeneracy implies sparsity, but it is stronger than average sparsity because it controls all subgraphs.
Degeneracy is important in graph algorithms because it allows efficient vertex orderings.
54.14 Arboricity
Arboricity measures how close a graph is to being a union of forests.
The arboricity of a graph is the minimum number of forests needed to cover all edges.
Sparse graphs usually have small arboricity.
For example:
| Graph | Arboricity |
|---|---|
| Forest | (1) |
| Planar graph | At most (3) |
| Complete graph (K_n) | Approximately (n/2) |
Arboricity appears in sparse graph algorithms and decomposition methods.
54.15 Expansion and Sparsity
Sparse graphs can behave very differently.
A tree is sparse and poorly connected.
An expander is sparse but highly connected.
Thus sparsity alone says little about global structure.
The crucial question is how the edges are arranged.
| Sparse graph type | Structural behavior |
|---|---|
| Tree | Fragile |
| Grid | Geometric |
| Expander | Highly connected |
| Random sparse graph | Probabilistic connectivity |
This diversity is one reason sparse graph theory is rich and difficult.
54.16 Dense Graph Limits
Dense graph sequences often exhibit statistical regularity.
For dense graphs, edge density becomes meaningful:
$$ \frac{m}{\binom{n}{2}}. $$
One studies limiting distributions of subgraphs, graphons, quasirandomness, and regularity lemmas.
Dense graph theory therefore tends toward probabilistic and analytic methods.
Sparse graph theory often requires combinatorial and geometric methods instead.
54.17 Sparse Graph Classes
Many important graph classes are sparse.
| Class | Sparsity source |
|---|---|
| Trees | Minimal connectivity |
| Planar graphs | Geometric constraints |
| Bounded-degree graphs | Local degree bounds |
| Minor-closed families | Structural restrictions |
| Geometric intersection graphs | Spatial constraints |
Sparse graph classes often admit specialized algorithms that are impossible in arbitrary dense graphs.
This is one reason sparse graph theory is central in modern algorithms.
54.18 Dense Subgraphs
Even sparse graphs may contain dense local regions.
For example, a social network may be globally sparse but contain tightly connected communities.
This leads to concepts such as:
| Concept | Meaning |
|---|---|
| Clique | Completely connected subgraph |
| Dense subgraph | Region with high edge concentration |
| Community | Strong internal connectivity |
| Core decomposition | Hierarchical dense regions |
Local density is often more important in applications than global density.
54.19 Common Mistakes
A common mistake is to identify sparsity with disconnectedness. Sparse graphs may still be highly connected.
Another mistake is to assume that dense graphs are always difficult to separate. Some dense graphs contain clear bottlenecks.
A third mistake is to confuse bounded degree with bounded density. One high-degree vertex does not make a graph dense.
A fourth mistake is to assume that sparse graphs are algorithmically trivial. Sparse graphs may still have complex global structure.
54.20 Summary
Sparse and dense graphs represent two broad structural regimes.
| Concept | Meaning |
|---|---|
| Sparse graph | Usually (m=O(n)) |
| Dense graph | Usually (m=\Theta(n^2)) |
| Average degree | (2m/n) |
| Sparse matrix | Adjacency matrix with mostly zero entries |
| Dense matrix | Adjacency matrix with many nonzero entries |
| Degeneracy | Local sparsity measure |
| Arboricity | Forest decomposition measure |
Sparsity and density influence connectivity, algorithms, matrix structure, random walks, expansion, and asymptotic graph behavior. They form one of the most basic distinctions in graph theory.