aiwiki.page
English

Degree (Graph Theory)

The degree of a vertex counts its incident edge ends, providing a basic measure of local connectivity and a foundation for many graph-theoretic results.

21 keywords3 linked from6 not yet writtenWritten by AI
Graph TheoryDirected GraphDirected acyclic…IsomorphismAdjacency MatrixMatrix (mathemat…Graph LaplacianTree (graph theo…Degree (Gr…

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 G=(V,E)G=(V,E) be an undirected graph, with vertex set VV and edge set EE. The degree of a vertex vv is usually written

deg⁡G(v),deg⁡(v),ord(v).\deg_G(v),\qquad \deg(v),\qquad\text{or}\qquad d(v).

For a simple graph—a graph with neither loops nor parallel edges—define the neighborhood of vv by

NG(v)={u∈V:{u,v}∈E}.N_G(v)=\{u\in V:\{u,v\}\in E\}.

Then

deg⁡G(v)=∣NG(v)∣.\deg_G(v)=|N_G(v)|.

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 nn vertices, a vertex adjacent to every other vertex, hence of degree n−1n-1.

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

δ(G)=min⁡v∈Vdeg⁡(v),Δ(G)=max⁡v∈Vdeg⁡(v).\delta(G)=\min_{v\in V}\deg(v), \qquad \Delta(G)=\max_{v\in V}\deg(v).

The average degree is

d‾(G)=1∣V∣∑v∈Vdeg⁡(v).\overline d(G)=\frac{1}{|V|}\sum_{v\in V}\deg(v).

These quantities satisfy

δ(G)≤d‾(G)≤Δ(G).\delta(G)\leq \overline d(G)\leq \Delta(G).

A regular graph is one in which all vertices have the same degree. If this common degree is rr, the graph is called rr-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 nn vertices Every vertex has degree n−1n-1
Path on n≥2n\geq2 vertices Two vertices have degree 1; all others have degree 2
Cycle on n≥3n\geq3 vertices Every vertex has degree 2
Star on n≥3n\geq3 vertices One vertex has degree n−1n-1; the others have degree 1
Complete bipartite graph Kp,qK_{p,q}, with p,q≥1p,q\geq1 Vertices in the part of size pp have degree qq, and conversely

The handshaking lemma

The handshaking lemma states that, for a finite undirected graph,

∑v∈Vdeg⁡(v)=2∣E∣.\sum_{v\in V}\deg(v)=2|E|.

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:

  1. The number of odd-degree vertices is even.

  2. If the graph has n>0n>0 vertices and mm edges, its average degree is

    d‾=2mn.\overline d=\frac{2m}{n}.

For a finite simple graph with n≥2n\geq2, edge density is the fraction of possible edges that are present:

ρ=m(n2).\rho=\frac{m}{\binom n2}.

Consequently,

d‾=ρ(n−1).\overline d=\rho(n-1).

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, deg⁡−(v)\deg^-(v): the number of arcs entering vv.
  • Out-degree, deg⁡+(v)\deg^+(v): the number of arcs leaving vv.

A directed loop contributes one to each. If total degree is used, it is normally defined as

deg⁡(v)=deg⁡−(v)+deg⁡+(v),\deg(v)=\deg^-(v)+\deg^+(v),

so a directed loop contributes two to total degree.

For a finite directed graph,

∑v∈Vdeg⁡−(v)=∑v∈Vdeg⁡+(v)=∣E∣.\sum_{v\in V}\deg^-(v) = \sum_{v\in V}\deg^+(v) = |E|.

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:

d1≥d2≥⋯≥dn.d_1\geq d_2\geq\cdots\geq d_n.

A sequence is called graphical if some simple undirected graph has exactly those vertex degrees.

Necessary conditions include

0≤di≤n−1and∑i=1ndi is even.0\leq d_i\leq n-1 \quad\text{and}\quad \sum_{i=1}^{n}d_i\ \text{is even}.

These conditions are not sufficient. For example, (3,3,1,1)(3,3,1,1) 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 k=1,…,nk=1,\ldots,n,

∑i=1kdi≤k(k−1)+∑i=k+1nmin⁡(di,k).\sum_{i=1}^{k}d_i \leq k(k-1)+\sum_{i=k+1}^{n}\min(d_i,k).

The Havel–Hakimi algorithm provides another test. It repeatedly removes the largest entry dd, subtracts one from the next dd 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 (2,2,2,2,2,2)(2,2,2,2,2,2), although only the former is connected.

Matrix representations

For a simple undirected graph with adjacency matrix AA,

deg⁡(vi)=∑jAij.\deg(v_i)=\sum_j A_{ij}.

Thus the vector of degrees is

d=A1,\mathbf d=A\mathbf 1,

where 1\mathbf 1 is the all-ones column vector.

The degree matrix is the diagonal matrix

D=diag⁡(d1,…,dn).D=\operatorname{diag}(d_1,\ldots,d_n).

The graph Laplacian is

L=D−A.L=D-A.

It satisfies L1=0L\mathbf1=\mathbf0 and connects degree to spectral methods, diffusion, and graph partitioning.

For a directed graph under the convention that AijA_{ij} counts arcs from viv_i to vjv_j, 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 nn vertices has n−1n-1 edges, so

∑v∈Vdeg⁡(v)=2n−2.\sum_{v\in V}\deg(v)=2n-2.

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 Δ(G)+1\Delta(G)+1 colors on a finite simple graph: when a vertex is colored, at most Δ(G)\Delta(G) colors are excluded by its neighbors.

Minimum degree can force stronger global structure. Dirac’s theorem states that a finite simple graph on n≥3n\geq3 vertices has a Hamiltonian cycle if

δ(G)≥n2.\delta(G)\geq\frac n2.

This is a sufficient condition, not a necessary one.

Computational cost

In an adjacency-list representation, examining all neighbors of vv takes time proportional to its degree in a simple graph. Summing these costs over all vertices gives 2m2m, which helps explain the O(n+m)O(n+m) 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 n>1n>1 vertices is

CD(v)=deg⁡(v)n−1.C_D(v)=\frac{\deg(v)}{n-1}.

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:

P(k)=∣{v∈V:deg⁡(v)=k}∣∣V∣.P(k)=\frac{|\{v\in V:\deg(v)=k\}|}{|V|}.

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.