In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge).
The distinction of what constitutes a dense or sparse graph is ill-defined, and is often represented by 'roughly equal to' statements.
Due to this, the way that density is defined often depends on the context of the problem.
The graph density of simple graphs is defined to be the ratio of the number of edges |E| with respect to the maximum possible edges.
The maximum number of edges for an undirected graph is
[1] For families of graphs of increasing size, one often calls them sparse if
Sometimes, in computer science, a more restrictive definition of sparse is used like
Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite subgraphs with density greater than its upper density.
Formally, the upper density of a graph G is the infimum of the values α such that the finite subgraphs of G with density α have a bounded number of vertices.
It can be shown using the Erdős–Stone theorem that the upper density can only be 1 or one of the superparticular ratios 0, 1/2, 2/3, 3/4, 4/5, … n/n + 1[2] Lee & Streinu (2008) and Streinu & Theran (2009) define a graph as being (k, l)-sparse if every nonempty subgraph with n vertices has at most kn − l edges, and (k, l)-tight if it is (k, l)-sparse and has exactly kn − l edges.
[3] Other graph families not characterized by their sparsity can also be described in this way.
For instance the facts that any planar graph with n vertices has at most 3n – 6 edges (except for graphs with fewer than 3 vertices), and that any subgraph of a planar graph is planar, together imply that the planar graphs are (3,6)-sparse.
Streinu and Theran show that testing (k,l)-sparsity may be performed in polynomial time when k and l are integers and 0 ≤ l < 2k.
[4] For a graph family, the existence of k and l such that the graphs in the family are all (k,l)-sparse is equivalent to the graphs in the family having bounded degeneracy or having bounded arboricity.
[6] Nešetřil & Ossona de Mendez (2010) considered that the sparsity/density dichotomy makes it necessary to consider infinite graph classes instead of single graph instances.
To the contrary, if such a threshold does not exist, the class is nowhere dense.