Boundeddegree

Bounded-degree refers to a property of a graph in which there exists a fixed constant Δ such that every vertex has degree at most Δ. More formally, a graph G = (V,E) has bounded degree if there exists Δ ∈ N with deg(v) ≤ Δ for all v ∈ V. The smallest such Δ is the maximum degree, denoted Δ(G). When this bound does not depend on the size of the graph, the graph is said to have bounded degree. A direct consequence is that the number of edges satisfies |E| ≤ Δ|V|/2, so bounded-degree graphs are sparse.

Examples and distinctions: Paths and cycles have maximum degree at most 2; trees have a maximum degree equal to the largest degree of any vertex in the tree; planar grids typically have a small fixed Δ. Regular graphs with degree Δ are a special case where every vertex has degree exactly Δ. In contrast, complete graphs K_n have maximum degree n−1, which grows with the graph size and is not bounded.

Consequences and applications: Many algorithms rely on bounded-degree inputs to achieve favorable performance, often yielding linear time or space bounds with constants depending on Δ. In distributed computing, bounded degree helps bound message complexity in models such as LOCAL and CONGEST. In probabilistic and random graph theory, bounded-degree models assist the analysis of locality, mixing times, and percolation phenomena.

Related concepts: Bounded-degree graphs are a form of sparsity and relate to degeneracy, since a graph with maximum degree Δ has degeneracy at most Δ. The notion extends to generalized settings such as bounded-degree hypergraphs and directed graphs, where bounds may be placed on in-degrees or out-degrees.