1 Definition
The maximum degree of a graph is the largest degree attained by any vertex in the graph. It summarizes how highly connected the most connected vertex is and gives a simple numerical description of local complexity. For a graph \(G\), this value is commonly written as \(\Delta(G)\).
1.1 Degree of a vertex
The degree of a vertex is the number of edges incident to it. In a simple undirected graph, each edge contributes one to the degree of each of its two endpoints. A vertex with degree 0 is isolated, while a vertex of degree 1 is called a leaf or pendant vertex in many contexts.
1.2 Maximum degree of a graph
The maximum degree is obtained by examining all vertices and selecting the largest degree among them. If the vertex set of a graph is \(V(G)\), then the maximum degree is
\[ \Delta(G)=\max\{d(v):v\in V(G)\}, \]
where \(d(v)\) denotes the degree of vertex \(v\). This parameter is often used to compare graphs that differ in size but share similar local structure.
1.3 Notation
The notation for maximum degree is usually compact, since it appears frequently in graph-theoretic formulas and theorems. The symbol is chosen to fit naturally with related degree parameters such as minimum degree and average degree.
1.3.1 Common symbols
The most common notation is \(\Delta(G)\). When the graph is clear from context, writers often shorten this to \(\Delta\). In informal discussion, the phrase “maximum degree” is sometimes used without a symbol.
1.3.2 Alternative conventions
Some texts use \(d_{\max}(G)\) or \(\Delta_G\) instead of \(\Delta(G)\). In specialized areas, especially algorithm analysis or network science, the same quantity may be described as the maximum node degree or maximum valence.
2 Basic properties
The maximum degree is closely linked to other degree-based quantities and gives immediate information about the shape of a graph. Although simple to define, it has useful consequences for coloring, connectivity estimates, and sparsity bounds.
2.1 Relationship to minimum degree
The minimum degree, usually denoted \(\delta(G)\), is the smallest degree among the vertices of \(G\). For every graph,
\[ \delta(G)\le \Delta(G). \]
The gap between these two values can indicate whether a graph is relatively uniform or highly uneven. In regular graphs, the two quantities are equal.
2.2 Relationship to average degree
The average degree measures the mean number of incident edges per vertex. In an undirected graph with \(n\) vertices and \(m\) edges, the average degree is \(2m/n\). Since the maximum degree is at least as large as the average degree,
\[ \frac{2m}{n}\le \Delta(G). \]
This inequality is immediate from the fact that the maximum of a set of numbers cannot be smaller than their average.
2.3 Bounds and inequalities
The maximum degree is constrained by the size of the graph and by its number of edges. Such bounds are often used to estimate structural complexity without listing every vertex degree individually.
2.3.1 In terms of the number of vertices
For a simple graph with \(n\) vertices, the maximum degree satisfies
\[ 0\le \Delta(G)\le n-1. \]
The upper bound reflects the fact that a vertex can be adjacent to at most all other vertices. The bound is attained by complete graphs, where every vertex is connected to every other vertex.
2.3.2 In terms of the number of edges
If a graph has \(m\) edges, then no vertex can have degree greater than \(m\), because each incident edge must be distinct. Thus,
\[ \Delta(G)\le m. \]
This bound is often loose, but it is immediate and useful in sparse settings.
3 Examples
Examples help show how maximum degree varies across familiar graph families. The value may be constant, small, or grow with the size of the graph depending on the topology.
3.1 Simple graphs
In a graph consisting of a single edge, the two endpoints each have degree 1, so the maximum degree is 1. In a graph with no edges, every vertex has degree 0 and the maximum degree is 0. More complicated simple graphs may have a wide range of vertex degrees.
3.2 Complete graphs
In the complete graph \(K_n\), every vertex is adjacent to all other vertices. Therefore each vertex has degree \(n-1\), and
\[ \Delta(K_n)=n-1. \]
This is the largest possible maximum degree among simple graphs on \(n\) vertices.
3.3 Path graphs
In a path graph \(P_n\) with \(n\ge 2\), the two end vertices have degree 1 and the interior vertices have degree 2. Consequently,
\[ \Delta(P_n)=2 \]
for all \(n\ge 3\), while \(\Delta(P_2)=1\).
3.4 Cycle graphs
In a cycle graph \(C_n\) with \(n\ge 3\), each vertex has degree 2. Thus the maximum degree is always
\[ \Delta(C_n)=2. \]
Cycle graphs are examples of 2-regular graphs.
3.5 Star graphs
A star graph has one central vertex connected to all other vertices, while the outer vertices each have degree 1. For the star on \(n\) vertices,
\[ \Delta = n-1. \]
This makes the star graph an extreme example of uneven degree distribution.
4 Related graph parameters
Maximum degree is one of several standard measures used to summarize the degree structure of a graph. It is often interpreted together with parameters that describe the lower, central, or overall degree behavior.
4.1 Minimum degree
The minimum degree, \(\delta(G)\), identifies the least connected vertex. Together with \(\Delta(G)\), it provides a range for the degrees present in the graph. A narrow range suggests uniformity, while a wide range points to heterogeneity.
4.2 Average degree
Average degree reflects the typical level of local connectivity in the graph. Unlike maximum degree, it is influenced by all vertices rather than just the most connected one. Comparing the two can reveal whether a graph contains a few unusually high-degree vertices.
4.3 Degree sequence
The degree sequence is the list of vertex degrees, usually arranged in nonincreasing order. The maximum degree is simply the first entry in this ordered list. Degree sequences are used in graph reconstruction, characterization, and graphicality tests.
4.4 Regular graphs
A graph is regular if every vertex has the same degree. In a \(k\)-regular graph, the maximum degree, minimum degree, and average degree are all equal to \(k\). Regular graphs provide a highly symmetric case in which maximum degree carries complete information about the degree distribution.
4.5 Graph density
Graph density measures how many edges a graph has relative to the maximum possible number. Dense graphs often have larger maximum degree, though the two concepts are not identical. A graph may have high density without every vertex having high degree, and vice versa.
5 Applications
Maximum degree appears in many theoretical and practical settings because it controls local load, adjacency complexity, and certain worst-case behaviors. It is especially useful when a single vertex can dominate the structure.
5.1 Coloring and scheduling
In vertex coloring, a classical upper bound states that a simple graph can be colored with at most \(\Delta(G)+1\) colors by a greedy procedure. This makes maximum degree a key parameter in coloring heuristics and proofs. In scheduling problems, it can represent the largest number of conflicts or constraints affecting a task.
5.2 Network design
In network models, maximum degree can indicate the busiest router, hub, or intersection. Limiting maximum degree may help distribute traffic more evenly and avoid single points of overload. In design problems, a small maximum degree is often associated with simpler and more robust local connectivity.
5.3 Algorithm analysis
Many graph algorithms run in time that depends on degrees of vertices, so the maximum degree can affect worst-case performance. For example, procedures that inspect all neighbors of a vertex may behave differently on graphs with large hubs than on graphs with bounded degree. As a result, \(\Delta(G)\) is often used in complexity estimates for sparse graph algorithms.
6 Variants and extensions
The notion of maximum degree extends naturally to several broader graph models. In each setting, the definition adapts to the relevant notion of incidence.
6.1 Directed graphs
In a directed graph, each vertex has both an in-degree and an out-degree. Because edges have orientation, a single degree value is usually not sufficient to describe local connectivity.
6.1.1 Maximum in-degree
The maximum in-degree is the largest number of incoming edges among all vertices. It measures the most heavily targeted vertex in the digraph and is often written as \(\Delta^-(G)\) or similar notation.
6.1.2 Maximum out-degree
The maximum out-degree is the largest number of outgoing edges from any vertex. It is often denoted \(\Delta^+(G)\). This quantity is relevant in flow models, dependency graphs, and search procedures.
6.2 Multigraphs
In a multigraph, multiple edges may connect the same pair of vertices. Degrees are counted with multiplicity, so parallel edges increase the degree accordingly. The maximum degree may therefore exceed what would be possible in a simple graph with the same number of vertices.
6.3 Hypergraphs
In hypergraphs, an edge can contain more than two vertices. The degree of a vertex is then the number of hyperedges containing it, or sometimes a weighted variant depending on the convention. Maximum degree again records the largest such value and can be used to study sparsity and incidence structure.
7 Computational aspects
Because maximum degree is easy to define and straightforward to compute, it is commonly used in graph-processing routines. Its practical value lies in both its simplicity and its relevance to worst-case analysis.
7.1 Computing the maximum degree
If a graph is given by adjacency lists, the degree of each vertex can be read directly from the length of its list, and the maximum can be found by scanning all vertices. With an adjacency matrix, one may count the nonzero entries in each row or column for an undirected graph. In either case, the result is obtained by a complete pass through the representation.
7.2 Complexity considerations
For a graph with \(n\) vertices and \(m\) edges, computing the maximum degree is typically linear in the size of the input representation. Using adjacency lists, this is often \(O(n+m)\). If degrees are already maintained dynamically, the maximum may be available immediately or with very little extra work.
7.3 Data structures for degree tracking
Dynamic graph algorithms may update degrees as edges are inserted or removed. Common approaches include arrays of degree counts, heaps for tracking the current largest degree, and auxiliary tables for bucket-based methods. These structures support efficient updates when the graph changes repeatedly.
8 See also
8.1 Degree (graph theory)
A general notion describing how many edges are incident to a vertex.
8.2 Vertex degree
The degree of an individual vertex in a graph.
8.3 Handshaking lemma
The identity stating that the sum of all vertex degrees equals twice the number of edges in an undirected graph.