In graph theory, the degree of a vertex is the number of edge ends incident with it. In an undirected graph without loops or parallel edges, this is simply the number of its neighbors. A loop contributes two to the degree of its vertex, while parallel edges are counted separately. Degree describes local connectivity and is fundamental to the study of graph structure, traversal, coloring, and networks.
Definition and conventions
Let be an undirected graph, with vertex set and edge set . The degree of a vertex is usually written
For a simple graph—a graph with neither loops nor parallel edges—define the neighborhood of by
Then
The distinction between incident edges and incident edge ends matters when loops are allowed. A loop has both ends at the same vertex and therefore contributes two to its degree. For example, a vertex incident with two ordinary edges and one loop has degree four.
In a multigraph, distinct edges may join the same pair of vertices. Each contributes separately to degree, so degree need not equal the number of distinct neighbors. A vertex joined to one other vertex by three parallel edges has degree three but only one distinct neighbor.
Common terms include:
- Isolated vertex: a vertex of degree zero.
- Leaf or pendant vertex: a vertex of degree one.
- Even vertex or odd vertex: a vertex whose degree is even or odd.
- Universal vertex: in a simple graph with vertices, a vertex adjacent to every other vertex, hence of degree .
Unless otherwise specified, numerical identities involving sums of degrees concern finite graphs.
Minimum, maximum, and average degree
For a finite graph with at least one vertex, the minimum and maximum degrees are
The average degree is
These quantities satisfy
A regular graph is one in which all vertices have the same degree. If this common degree is , the graph is called -regular. A finite simple 2-regular graph is a disjoint union of cycles; a 3-regular graph is also called a cubic graph.
Some standard examples illustrate the distinction between local and global structure:
| Graph | Vertex degrees |
|---|---|
| Complete graph on vertices | Every vertex has degree |
| Path on vertices | Two vertices have degree 1; all others have degree 2 |
| Cycle on vertices | Every vertex has degree 2 |
| Star on vertices | One vertex has degree ; the others have degree 1 |
| Complete bipartite graph , with | Vertices in the part of size have degree , and conversely |
The handshaking lemma
The handshaking lemma states that, for a finite undirected graph,
Its proof is a double count: every edge has two ends and contributes exactly two to the sum, including when both ends belong to the same vertex. This explains why loops are counted twice.
Two immediate consequences are:
The number of odd-degree vertices is even.
If the graph has vertices and edges, its average degree is
For a finite simple graph with , edge density is the fraction of possible edges that are present:
Consequently,
Degree and density therefore measure related but different features: degree describes connectivity around vertices, whereas density normalizes the total edge count by graph size.
Directed graphs
In a directed graph, each edge, or arc, has a source and a target. Degree splits into two quantities:
- In-degree, : the number of arcs entering .
- Out-degree, : the number of arcs leaving .
A directed loop contributes one to each. If total degree is used, it is normally defined as
so a directed loop contributes two to total degree.
For a finite directed graph,
A vertex with in-degree zero is often called a source, and one with out-degree zero a sink, though some conventions reserve these terms for nonisolated vertices. Every finite, nonempty directed acyclic graph has at least one vertex of in-degree zero and at least one of out-degree zero.
Degree sequences
A degree sequence lists the degrees of all vertices, usually in nonincreasing order:
A sequence is called graphical if some simple undirected graph has exactly those vertex degrees.
Necessary conditions include
These conditions are not sufficient. For example, satisfies both, but cannot be realized: the two degree-three vertices would each have to be adjacent to both degree-one vertices, forcing those vertices to have degree at least two.
The Erdős–Gallai theorem gives a complete characterization. A nonincreasing sequence of nonnegative integers is graphical if and only if its sum is even and, for every ,
The Havel–Hakimi algorithm provides another test. It repeatedly removes the largest entry , subtracts one from the next largest entries, and reorders the remaining sequence. The original sequence is graphical precisely when this process reaches an all-zero sequence without requiring an impossible subtraction.
A degree sequence generally does not determine a graph up to isomorphism. A cycle on six vertices and two disjoint triangles both have degree sequence , although only the former is connected.
Matrix representations
For a simple undirected graph with adjacency matrix ,
Thus the vector of degrees is
where is the all-ones column vector.
The degree matrix is the diagonal matrix
The graph Laplacian is
It satisfies and connects degree to spectral methods, diffusion, and graph partitioning.
For a directed graph under the convention that counts arcs from to , row sums give out-degrees and column sums give in-degrees.
When undirected loops are allowed, adjacency-matrix conventions differ: a loop may be represented by one or by two on the diagonal. The row-sum identity for degree requires diagonal entries that count each loop twice.
Structural and algorithmic significance
Degree conditions often constrain global properties, but their implications depend on additional assumptions.
Trees and edge traversal
A finite tree with vertices has edges, so
Every finite tree with at least two vertices has at least two leaves.
Degree parity also characterizes Eulerian trails, which use every edge exactly once. For a finite undirected graph with at least one edge, suppose all nonisolated vertices lie in one connected component. The graph has:
- an Eulerian circuit if and only if every vertex has even degree;
- an open Eulerian trail if and only if exactly two vertices have odd degree.
In the second case, the odd-degree vertices are the endpoints of the trail.
Coloring and Hamiltonian cycles
A greedy vertex-coloring algorithm uses at most colors on a finite simple graph: when a vertex is colored, at most colors are excluded by its neighbors.
Minimum degree can force stronger global structure. Dirac’s theorem states that a finite simple graph on vertices has a Hamiltonian cycle if
This is a sufficient condition, not a necessary one.
Computational cost
In an adjacency-list representation, examining all neighbors of takes time proportional to its degree in a simple graph. Summing these costs over all vertices gives , which helps explain the running time of standard graph-traversal algorithms, using big-O notation.
Network applications and limitations
In network analysis, degree measures the number of direct connections associated with a node. Normalized degree centrality in a simple graph with vertices is
For directed networks, in-degree and out-degree are usually treated separately because incoming and outgoing connections may have different meanings.
The degree distribution records the fraction of vertices having each degree:
If a vertex is selected uniformly at random, its degree is a random variable with this distribution, and its expected value is the average degree.
Degree is local: it does not reveal how a vertex’s neighbors are connected, whether it bridges distant regions, or how far it lies from other vertices. Networks with the same degree sequence can differ in connectivity, clustering, and path lengths.
For weighted networks, the sum of incident edge weights is often called strength or weighted degree. This must be distinguished from ordinary degree, which counts edge ends rather than connection weights. Likewise, observing a broad degree distribution does not by itself establish a power law.
Infinite graphs
In an infinite graph, a vertex may have finite or infinite degree. A graph is locally finite if every vertex has finite degree, even when the graph has infinitely many vertices.
Infinite degrees can be expressed using cardinal numbers. Finite parity arguments do not extend unchanged: a one-way infinite path has exactly one odd-degree vertex—its initial vertex has degree one, while every other vertex has degree two. Thus the statement that the number of odd-degree vertices is even requires finiteness.