Fact-checked by Grok 2 weeks ago

Dense graph

In graph theory, a dense graph is a graph in which the number of edges is close to the theoretical maximum possible for a given number of vertices n, typically on the order of O(n^2), resulting in high connectivity among vertices.^[1] For an undirected simple graph, the maximum number of edges is \frac{n(n-1)}{2}, and the graph density D is calculated as D = \frac{2|E|}{n(n-1)}, where |E| is the number of edges; dense graphs exhibit D values approaching or exceeding 0.5, often near 1.^[2] This contrasts with sparse graphs, where the edge count is much lower, typically O(n) or O(n \log n), leading to densities close to 0.^[2] Dense graphs are fundamental in algorithm design and data structures, as their representation via an adjacency matrix—a 2D array of size n \times n—is space-efficient and allows O(1) edge queries, making it suitable for operations like transitive closure or all-pairs shortest paths (e.g., Floyd-Warshall algorithm).^[1] In contrast, adjacency lists are less optimal for dense graphs due to higher space overhead for edge storage. Examples include nearly complete graphs like the complete graph K_n, where every pair of vertices is connected, or social network models assuming high interaction density.^[1] In extremal graph theory, dense graphs are studied for their guaranteed substructures, such as cliques or other dense subgraphs. Applications span network analysis, where dense subgraphs indicate communities, to optimization problems like dense subgraph detection for anomaly identification in data mining.^[2]

Fundamentals

Definition

In graph theory, a simple undirected graph is defined as a pair G = (V, E), where V is a finite nonempty set of vertices and E is a subset of \binom{V}{2}, the set of all unordered pairs of distinct vertices from V, with no multiple edges between the same pair of vertices or self-loops. The theoretical maximum number of edges in such a graph with n = |V| vertices is \binom{n}{2} = \frac{n(n-1)}{2}.^[3] A dense graph is one in which the number of edges |E| is close to this maximum possible value, meaning the graph contains a substantial proportion of all potential connections between its vertices.^[4] Informally, dense graphs typically have \Theta(n^2) edges, indicating quadratic growth in the number of edges relative to the number of vertices.^[5] More formally, in asymptotic analysis, a graph is considered dense if it possesses \Theta(n^2) edges, or equivalently, if its edge density—defined as the ratio d(G) = \frac{2|E|}{n(n-1)}—is \Theta(1), meaning bounded below by a positive constant independent of n. Complete graphs achieve the maximum density of 1 and represent the extremal case of dense graphs, while other dense graphs may have lower but still constant densities.^[3]

Examples

The complete graph K_n, which features every pair of n vertices connected by an edge, exemplifies the extremal case of a dense graph, possessing precisely \binom{n}{2} edges and achieving the maximum possible density of 1.^[6] In this construction, no additional edges can be added without altering the vertex set, making K_n a benchmark for full connectivity in graph theory.^[7] Random graphs from the Erdős–Rényi model G(n,p), where each possible edge among n vertices is included independently with fixed probability p > 0, provide another illustration of dense graphs, as the expected number of edges is approximately p \binom{n}{2}, which grows quadratically with n and yields a density approaching p.^[8] These models are particularly useful for studying probabilistic properties of dense structures, where the fixed p ensures a non-vanishing proportion of edges relative to the complete graph.^[9] Complete bipartite graphs K_{a,b}, with partitions of sizes a and b both on the order of n/2, demonstrate dense behavior in a balanced two-part structure, where the edge count is ab and the density approaches $1/2 as n increases.^[10] This configuration highlights how density can remain substantial even without edges within partitions, offering a contrast to fully complete graphs while maintaining high connectivity across the bipartition.^[11] Turán graphs T(n,r), which are the complete r-partite graphs on n vertices with balanced part sizes and no edges within parts, serve as near-complete dense examples for large r, avoiding cliques of size r+1 while approaching the density of K_n as r grows.^[12] These extremal graphs maximize edges under forbidden subgraph constraints, illustrating dense constructions in extremal graph theory.^[13] In real-world applications, dense graphs model social networks with high interconnectivity, such as tight-knit communities where most individuals maintain friendships with nearly all others, akin to dense friendship graphs that facilitate rapid information spread.^[14] Such examples underscore the practical relevance of dense structures in analyzing cohesive groups within larger networks.^[15]

Density Measures

Edge Density

The edge density of a simple undirected graph G = (V, E) is defined as the ratio of the number of edges |E| to the maximum possible number of edges in a complete graph on |V| vertices, given by the formula

d(G) = \frac{|E|}{\binom{|V|}{2}} = \frac{2|E|}{|V|(|V|-1)},

where n = |V| and \binom{n}{2} = \frac{n(n-1)}{2}. This measure yields a value between 0 (for the empty graph) and 1 (for the complete graph K_n). A graph density d(G) > 1/2 indicates that the graph contains more than half of the possible edges. As d(G) approaches 1, the graph becomes increasingly dense, approaching the structure of a complete graph. In asymptotic terms, a graph is considered dense if its edge density satisfies d(G) = \Theta(1) or more generally \Omega(1), corresponding to \Theta(n^2) or at least \Omega(n^2) edges as n \to \infty.^[16] For example, consider a graph with n = 100 vertices and m = 4000 edges; the density is d(G) = 4000 / \binom{100}{2} = 4000 / 4950 \approx 0.81, indicating a highly dense structure. The edge density is closely related to the average degree \overline{d}(G) = 2|E|/|V|, since d(G) = \overline{d}(G) / (n-1), which for large n approximates \overline{d}(G) / n; thus, high density implies a linear average degree in n.

Upper Density

In extremal graph theory, the upper density of a graph G, denoted \bar{d}(G), is defined as

\bar{d}(G) = \limsup_{n \to \infty} \max_{\substack{H \subseteq G \\ |V(H)| = n}} d(H),

where the maximum is taken over all induced subgraphs H of G with n vertices, and d(H) = \frac{|E(H)|}{\binom{n}{2}} is the edge density of H. This definition quantifies the highest asymptotic density achievable in arbitrarily large finite induced subgraphs of G, providing a measure of the "densest" local structure within G. The formula arises by considering a sequence of induced subgraphs H_n of G with |V(H_n)| = n that maximize d(H_n) for each n, and then taking the limit superior of d(H_n) as n \to \infty. This limsup captures the supremum of densities over all such sequences, reflecting the potential for dense substructures even if the overall graph is not uniformly dense. In contrast to the global edge density of a single finite graph, upper density focuses on asymptotic behavior across growing subgraphs. Upper density is instrumental in extremal graph theory for bounding the edge counts in graphs avoiding specific forbidden subgraphs. For example, the Erdős–Stone theorem establishes that if \bar{d}(G) > 1 - \frac{1}{r-1} for some integer r \geq 2, then G contains large complete r-partite subgraphs. A representative example is the class of bipartite graphs, which avoid triangles (K_3) and thus have \bar{d}(G) \leq \frac{1}{2} by the Erdős–Stone theorem, as the Turán graph T(n,2) achieves density \frac{1}{2}. In contrast, complete graphs K_\infty (the infinite clique) have \bar{d}(G) = 1, as every finite induced subgraph is complete. The concept of upper density was introduced by Paul Erdős and Arthur Stone in their 1946 paper addressing Turán-type problems on the maximum number of edges in graphs without certain complete bipartite subgraphs, laying foundational groundwork for modern extremal results.^[17]

Lower Density

The lower density of a graph G, denoted \underline{d}(G), is defined as \underline{d}(G) = \liminf_{n \to \infty} \min_{H \subseteq G, |V(H)|=n} d(H), where d(H) is the edge density of the induced subgraph H and the minimum is taken over all induced subgraphs H on exactly n vertices. This measure captures the guaranteed minimum edge density persisting in the sparsest large induced subgraphs of G, providing a notion of uniform lower bound on subgraph densities as the graph size grows. It contrasts with average or maximum densities by focusing on the infimum behavior, ensuring no large induced subgraph becomes arbitrarily sparse. Equivalently, \underline{d}(G) = \liminf_{n \to \infty} \frac{|E(H_n)|}{\binom{n}{2}}, where H_n ranges over all induced subgraphs of G on n vertices that achieve the minimum number of edges. Graphs with \underline{d}(G) > 0 are termed uniformly dense, as they resist the formation of sparse large induced subgraphs, maintaining a positive edge proportion throughout. This property implies stability against sparsity, where every sufficiently large induced subgraph retains a density bounded away from zero by \underline{d}(G). In the context of hereditary graph classes—collections closed under taking induced subgraphs—the lower density plays a key role in bounding uniform density across the class. For such a class \mathcal{P}, the lower density \underline{d}(\mathcal{P}) ensures that every graph in \mathcal{P} of sufficiently large order has all its large induced subgraphs (and thus all members of \mathcal{P}) with density at least \underline{d}(\mathcal{P}), preventing the inclusion of arbitrarily sparse large graphs while preserving the hereditary structure. A representative example occurs in the Erdős–Rényi random graph model G(n, 1/2), where edges are included independently with probability $1/2. Almost surely, both the upper and lower densities equal $1/2, as the model produces quasirandom graphs where the edge density in every induced subgraph on \Theta(n) vertices concentrates around $1/2.^[18]

Comparisons with Sparse Graphs

Sparse Graphs

A sparse graph is a graph G = (V, E) with n = |V| vertices and m = |E| edges such that m = o(n^2), meaning the number of edges grows slower than quadratically in the number of vertices.^[19] Equivalently, the density d(G) = \frac{2m}{n(n-1)} satisfies d(G) \to 0 as n \to \infty.^[6] This scarcity of edges distinguishes sparse graphs from their dense counterparts, where edge counts approach the maximum possible \Theta(n^2). Key structural properties of sparse graphs include a sublinear average degree \delta_{\text{avg}} = \frac{2m}{n} = o(n), which often bounds to a constant or low-order term in practical cases with m = O(n) edges.^[20] Prominent examples encompass trees, which contain exactly n-1 edges and form minimally connected sparse structures,^[21] and planar graphs, which admit at most $3n - 6 edges for n \geq 3 due to embedding constraints derived from Euler's formula.^[22] Asymptotic classes of sparse graphs typically feature O(n^{1+\epsilon}) edges for any fixed \epsilon < 1, encompassing subquadratic regimes studied in algorithmic and extremal graph theory.^[23] A representative example is the cycle graph C_n, which has precisely n edges and density \approx \frac{2}{n} \to 0 as n \to \infty, illustrating linear edge growth in a connected sparse structure.^[2] The edge paucity in sparse graphs yields practical implications, such as efficient storage via adjacency lists requiring O(n + m) space—far less than the O(n^2) needed for dense representations like adjacency matrices—and enables faster algorithmic processing for tasks like traversal or shortest paths, often in linear or near-linear time relative to m.^[4] In contrast to dense graphs, this low density facilitates scalability in applications modeling real-world networks with limited connections.

Tight Graphs

Tight graphs form a specialized subclass of sparse graphs, particularly in contexts like rigidity theory or connectivity, that attain the precise minimum number of edges required to satisfy a designated structural property (e.g., (k,l)-tightness where e = k v - l globally and for subgraphs), while ensuring no superfluous edges exist. In this context, a graph is tight if removing any edge violates the property, making these structures extremal within sparsity constraints. This minimality is often formalized through sparsity counts, where tight graphs meet equality in both global and local edge bounds for the property.^[24] A classic illustration of tight graphs arises in connectivity: trees are minimally connected structures with exactly n-1 edges for n vertices, achieving (1,1)-tightness under sparsity conditions where every subgraph satisfies e' \leq v' - 1 edges, with global equality. Spanning trees exemplify this in broader graphs, providing essential connectivity with the fewest possible edges while preserving overall reachability. Similarly, in rigidity theory, maximally outerplanar structures achieve the bound of $2n-3 edges, ensuring planarity and outerplanarity without excess; these graphs are critically sparse, as adding edges may violate outerplanarity or removing them disrupts the embedding. The defining property of no redundant edges underscores their role: any deletion alters the core attribute, such as rendering the graph non-outerplanar or non-connected. Harary graphs further exemplify tightness by constructing the sparsest k-connected graphs with n vertices and minimum degree k, using approximately \lceil k n / 2 \rceil edges in a circulant arrangement that minimizes density while guaranteeing the degree and connectivity conditions.^[24]^[25]^[26]^[27]

Graph Classes

Dense Graph Classes

Dense graph classes encompass several prominent families of graphs characterized by high edge densities and robust structural properties. The complete graph K_n, which features an edge between every pair of its n vertices, represents the extremal case of density, achieving a density of 1 with \binom{n}{2} edges.^[28] Its clique number equals n, as the entire graph forms a single clique.^[28] Turán graphs T(n,r) form another key class, defined as the complete r-partite graphs on n vertices with partite sets as equal in size as possible. These graphs attain an asymptotic density of $1 - \frac{1}{r} and maximize the number of edges among all K_{r+1}-free graphs on n vertices, as established by Turán's theorem.^[29] This extremal property underscores their role in avoiding large cliques while maintaining high connectivity. Random dense graphs, modeled by the Erdős–Rényi process G(n,p) with p = 1 - o(1), generate graphs that are almost complete with high probability, featuring only o(n^2) missing edges.^[8] In this regime, such graphs exhibit properties akin to complete graphs, including near-maximal clique sizes and edge counts approaching \binom{n}{2}.^[8] These classes share notable properties, such as elevated chromatic numbers: K_n requires n colors, T(n,r) needs exactly r colors, and dense G(n,p) demands nearly n colors with high probability.^[28]^[29]^[8] Hamiltonicity is also assured; for instance, Dirac's theorem guarantees a Hamiltonian cycle in any graph on n \geq 3 vertices with minimum degree at least n/2, a condition satisfied by these dense classes when their density exceeds $1/2. Ore's theorem extends this, ensuring Hamiltonicity if the sum of degrees of any non-adjacent vertices is at least n. In applications, dense graph classes model highly interconnected systems, such as the core structure of internet routing backbones at the autonomous system level, where k-dense communities capture persistent high-connectivity patterns amid growth.^[30]

Sparse Graph Classes

Sparse graph classes encompass families of graphs with structural properties that enforce sparsity, typically resulting in O(n) edges for n vertices, which facilitates efficient algorithmic solutions for complex problems. Bounded-degree graphs constitute a fundamental sparse class, where the maximum degree Δ is fixed, ensuring that no vertex connects to more than Δ others. The handshaking lemma implies that the sum of degrees is at most Δn, yielding at most Δn/2 edges overall.^[31] This bounded connectivity limits the graph's density and enables linear-time traversals and other operations proportional to the edge count. Planar graphs form another key class, characterized by their embeddability in the plane without edge crossings. For simple connected planar graphs with n ≥ 3 vertices, Euler's formula V - E + F = 2, combined with the observation that each face is bounded by at least three edges (leading to 2E ≥ 3F), establishes that the number of edges satisfies E ≤ 3n - 6.^[32] This bound underscores their sparsity and supports applications in geographic modeling and VLSI design. Graphs with bounded treewidth k represent a versatile sparse class, where the graph admits a tree decomposition of width at most k, capturing "tree-likeness" while allowing limited branching. Such graphs possess O(kn) edges, as exemplified by k-trees, which achieve exactly \binom{k+1}{2} + k(n - k - 1) edges.^[33] Bounded treewidth is central to parameterized complexity, enabling fixed-parameter tractable algorithms for problems intractable on general graphs.^[33] These classes share algorithmic advantages, including polynomial-time solvability for numerous NP-hard problems restricted to them. For instance, shortest paths in unweighted graphs can be computed via breadth-first search in O(n + m) time, leveraging the linear edge count. Grid graphs illustrate this sparsity: an m × n grid has mn vertices and approximately 2mn edges (precisely m(n-1) horizontal plus n(m-1) vertical), yielding O(n) edges when one dimension is fixed relative to the total vertices.^[34]

References

[1]
Dense Graph - GeeksforGeeks
Jul 23, 2025 · A dense graph is a type of graph where the number of edges is close to the maximum number of possible edges.
[2]
Graphs: Sparse vs Dense | Baeldung on Computer Science
Mar 18, 2024 · A density is some metric that tells us how “full” a graph is, in terms of the number of edges that it possesses, and in relation to the number ...
[3]
Graph Density -- from Wolfram MathWorld
The density of a simple graph is defined as the edge count m divided by the possible number of edges in the graph, i.e., rho(G) = (|E(G)|)/((|V(G)|; ...
[4]
CS106B Graph Algorithms - Stanford University
Mar 8, 2024 · A dense graph is one with a large number of edges (relative to the number of possible edges in that graph). (*) Note that different sources use ...
[5]
[PDF] CLRS B.4 Graph Theory Definitions Unit 1: DFS informally, a graph ...
graphs with Θ(n) edges are called sparse, those with Θ(n2) edges are dense ... Θ(n2), since it improves on sparser graphs. Remark. Ex.22.1-6 gives what's ...
[6]
[PDF] the graphon as a limit for dense graphs - UChicago Math
Although sparse graphs are more important from a practical point of view, this paper will focus on dense graphs because they have a more natural limit object ...
[7]
[PDF] Convergent sequences of dense graphs II. Multiway cuts and ...
Consider a dense sequence of simple graphs (Gn) such that the number of nodes in Gn goes to infinity with n (where, as usual, a graph is simple if it has no ...
[8]
[PDF] INTRODUCTION TO RANDOM GRAPHS
Sep 1, 2025 · degrees in dense random graphs. We then describe a simple canonical labelling algorithm for the graph isomorphism problem on a dense random ...
[9]
A note on the chromatic number of a dense random graph
Let G n , p denote the random graph on n labeled vertices, where each edge is included independently of the others with probability p . The chromatic number ...
[10]
[PDF] GRAPH THEORY WITH APPLICATIONS
This book is intended as an introduction to graph theory. Our aim has been to present what we consider to be the basic material, together with a wide.
[11]
Embedding into Bipartite Graphs | SIAM Journal on Discrete ...
Fischer, Refining the graph density condition for the existence of almost K-factors, Ars Combin. ... bipartite graph has a $K_{s,s}$-factor. Lower Bounds for Max- ...
[12]
A Density Turán Theorem | Journal of Graph Theory
Jun 1, 2017 · Bollobás, P.Erd's, and E.Szemerédi, On complete subgraphs of r -chromatic graphs, Discrete Math Volume 13 1975, pp.97-107.
[13]
Turán numbers of r-graphs on r + 1 vertices - ScienceDirect.com
Let ex ( n , H ) denote the Turán number of H which is the largest number of edges in an H-free r-graph with n vertices. The Turán density is π ( H ) = lim n → ...
[14]
[PDF] Lectures 2: Graph Theory and Social Networks
(Useful equation.) The density, ρ, of an undirected network is the fraction of all possible links that actually exist, given by m.
[15]
The Analysis of Social Networks - PMC - PubMed Central
This article reviews fundamentals of, and recent innovations in, social network analysis using a physician influence network as an example.
[16]
Graph Density | Baeldung on Computer Science
Mar 18, 2024 · Graph density represents the ratio between the edges present in a graph and the maximum number of edges that the graph can contain.
[17]
[PDF] Sparse graphs: metrics and random models - arXiv
Feb 10, 2010 · One might expect that graphs with Θ(n) edges are somehow simpler than denser graphs, but in fact the reverse is often the case, particularly for ...
[18]
[PDF] Algebraic graph theory The edge space of a graph is the vector ...
Weekly exercise. Definition. The upper density of an (infinite) graph is lim sup ¢. | R |. О|f Э |. П. : R ⊆ , R finite£. Corollary. The upper density of an ...
[19]
[PDF] Densities of Minor-Closed Graph Families - arXiv
Sep 28, 2010 · This definition of density can be extended to infinite graphs as the upper density: the upper density of an infinite graph G is the supremum ...<|control11|><|separator|>
[20]
None
### Definition of Upper Density for Infinite Graphs
[21]
On the structure of linear graphs - Project Euclid
December 1946 On the structure of linear graphs. P. Erdös, A. H. Stone. Bull. Amer. Math. Soc. 52(12): 1087-1091 (December 1946). ABOUT; FIRST PAGE; CITED BY.Missing: original | Show results with:original
[22]
https://www.cs.cornell.edu/courses/cs280/2001sp/handouts/h33.pdf
[23]
Sparse graphs using exchangeable random measures - PMC
Following Bollobás and Riordan (2009), we refer to graphs with Θ(n 2) edges as dense and graphs with o(n 2) edges as sparse (for notation, see Appendix C). The ...
[24]
A Graph's Density and Sparsity - Computer Science Stack Exchange
Mar 17, 2016 · From wikipedia: "In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite ...
[25]
[PDF] Lecture 11: Trees and forests 1 Counting edges in trees
By Theorem 1.2, that's the minimum number of edges in a graph with n vertices and k connected components.
[26]
[PDF] Planar graphs and coloring provide two extreme examples of prob
Apr 18, 2001 · Therefore 2e = S ≥ 3r. By Euler's formula, 2e ≥ 3(e − v + 2). Hence 2e ≥ 3e − 3v + 6, and e ≤ 3v − 6.
[27]
Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete ...
a phenomenon that ...
[28]
[PDF] Sparse and Tight Graphs in Rigidity Theory - maths.nuigalway.ie
Nov 11, 2016 · f G (G)=3v − e. Page 6. (k,l)-sparse and (k,l)-tight graphs. A simple graph G is (1,1)−tight if and only if G is a tree. A simple connected ...
[29]
Average connectivity of minimally 2-connected graphs and average ...
Jan 31, 2021 · We prove that every minimally 2-connected graph of order n with largest average connectivity is bipartite, with the set of vertices of degree 2 ...
[30]
[PDF] Complexity Results in Graph Reconstruction∗ - RIT
Oct 10, 2004 · It would be interesting to obtain tight (or tighter) bounds on the ... [Har71] Frank Harary. Graph Theory. Addison-Wesley, Reading, 2nd ...
[31]
[PDF] BROADCASTING IN HARARY GRAPHS - CORE
We present an additive approximation algorithm for the broadcast problem in Harary graph. We also provide some properties for the graph like vertex transitivity ...
[32]
Complete Graph -- from Wolfram MathWorld
### Summary of Complete Graph (K_n) from MathWorld
[33]
Turán Graph -- from Wolfram MathWorld
### Summary of Turán Graph T(n,r)
[34]
[PDF] Evolution of the Internet -Dense Structure - CAIDA
Abstract—As the Internet autonomous sytem (AS)-level topology grows over time, some of its structural properties remain unchanged.
[35]
[PDF] THE MAXIMUM NUMBER OF EDGES IN x*-FREE GRAPHS OF ...
We show that if G is 2K,-free and has maximum degree A(G) = D, then G has at most 5D2/4 edges if D is even. If D is odd, this bound can be improved to (5D* - ...
[36]
[PDF] 8 – Planar Graphs - William T. Trotter
Nov 14, 2017 · Proof of Euler's Formula ... Now consider a plane drawing of a triangle-free planar graph G on n vertices having the maximum number of edges.
[37]
[PDF] Tree Decompositions, Treewidth, and NP-Hard Problems A Survey ...
Abstract. This survey paper provides an introduction to the class of bounded treewidth graphs, for which many NP-hard problems can be solved effi- ciently.
[38]
[PDF] A Nearly-Linear Time Framework for Graph-Structured Sparsity
We introduce a framework for sparsity structures defined via graphs. Our approach is flexible and generalizes several previously studied spar- sity models.