Dense Graph

A graph whose edge population is a substantial, usually non-vanishing fraction of all possible vertex pairs, placing it in the quadratic-edge rather than sparse regime under a declared asymptotic convention.

Version

v3 · 2026-09-06 · History

Domain-specific #

1642

Origin domain

mathematics

Subdomain

graph theory

Aliases

Dense graph family, High-density graph

Core Idea

For a simple undirected graph (G=(V,E)) with (n=|V|), its normalized edge density is

\[ d(G)=\frac{|E|}{\binom n2}=\frac{2|E|}{n(n-1)}. \]

A dense graph has many edges relative to this ceiling. For a graph sequence, the clean asymptotic regime is \(|E|=\Theta(n^2)\), equivalently density bounded away from zero along the sequence. Contexts also use “dense” more informally for one graph close to complete, so the threshold must be declared.

Scope of Application

Dense graphs appear in extremal graph theory, random graphs, matrix-based algorithms, dense graph limits, clustering, and complement-based reasoning. Erdős–Stone connects positive edge density thresholds with forced complete multipartite subgraphs.

Clarity

State directedness, loops, multiplicity, normalization, graph size, and threshold. For families, report the limiting or limsup density. Never infer density from visualization alone.

Manages Complexity

The label routes a problem to the correct asymptotic and representation regime. Adjacency matrices can be appropriate; complement algorithms may be cheaper near completeness; edge-list methods optimized for (m=O(n)) lose their advantage. Density also supplies a normalized comparison across sizes.

Abstract Reasoning

1. Fix the graph model and edge ceiling.
2. Count vertices and edges.
3. Normalize density.
4. Choose finite or asymptotic semantics.
5. Inspect degree distribution so global density is not mistaken for uniformity.
6. Compare complement sparsity.
7. Apply dense-regime extremal, algorithmic, or limit tools.

Knowledge Transfer

The portable pattern is measure realized pairwise relations against the full pairwise opportunity space. It transfers to interaction matrices and relational databases. The proposed immediate parent is Network.

Relationships to Other Abstractions

Current abstraction Dense Graph Domain-specific

Parents (1) — more general patterns this builds on

• Dense Graph is a kind of Network Prime

  Network is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

• Dense Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space

Dense Graph sits in a sparse region of the domain-specific corpus (77^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Density, Distance & Planarity (11 abstractions)

Nearest neighbors

• Graph Sphericity — 0.84
• Goldberg–Seymour Theorem — 0.84
• Degree diameter problem — 0.82
• Pathwidth — 0.82
• Hosoya Index — 0.82

Computed from structural-signature embeddings · 2026-09-08