maximumdegree

Maximum degree, denoted Δ(G), is the largest vertex degree in a graph G = (V,E). The degree deg(v) of a vertex v is the number of edges incident to v; in a multigraph a loop contributes twice to the degree. Δ(G) = max{deg(v) : v ∈ V}. For a simple graph with n vertices, Δ ≤ n−1, and equality holds for the complete graph Kn. The sum of all vertex degrees equals 2|E| (the handshake lemma), so Δ(G) is at least the average degree d̄ = 2|E|/|V|.

Examples: In a path P3 the degrees are 1, 2, 1, so Δ = 2. In a star K1,n the center has degree n, so Δ = n. In Kn, every vertex has degree n−1, so Δ = n−1.

Computationally, Δ(G) is the maximum value in the degree sequence and can be found in linear time by counting degrees. It plays a role in various bounds and analyses: since d̄ ≤ Δ, the maximum degree provides information about overall connectivity. Brooks’ theorem relates Δ to the graph’s chromatic number: every connected graph G satisfies χ(G) ≤ Δ(G) except for the complete graphs and odd cycles, where χ(G) = Δ(G) + 1.

Related concepts include the minimum degree δ(G), the degree sequence, and regular graphs (where Δ = δ). In directed graphs, one distinguishes maximum out-degree, maximum in-degree, or total degree; the term maximum degree is sometimes used for total degree in that context.