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}.

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.