nearcomplete

Nearcomplete is a descriptive term used in mathematics and related fields to indicate that a structure nearly satisfies the defining properties of a complete object. The most common usage appears in graph theory, where a nearcomplete graph is one whose edge set is almost all possible edges for its number of vertices.

In graph-theoretic terms, a simple graph G with n vertices is nearcomplete if the number of missing edges is small relative to the total number of possible edges. Equivalently, the graph has edge density close to 1. A convenient way to express this is: for some small ε > 0, |E(G)| ≥ (1−ε) · C(n,2), where C(n,2) is the number of unordered vertex pairs. If ε can depend on n and tends to 0 as n grows, the graph is asymptotically nearcomplete. The degree condition δ(G) ≥ (1−ε)(n−1) is a related characterization that often implies near-completeness for large graphs.

Nearcomplete graphs behave similarly to complete graphs in many combinatorial and probabilistic arguments, though the few missing edges can influence exact outcomes. They serve as useful models in extremal graph theory, network design, and embedding problems, where high connectivity needs to be balanced against occasional omissions.

The term is sometimes extended to other mathematical structures that are almost complete, such as nearcomplete posets or matrices with mostly full entries. In practice, the precise threshold for “near completeness” depends on the context and the acceptable margin of imperfection for a given problem. See also complete graph, dense graph, and almost-complete.