Degree

Link

This note lacks links.

In graph theory, the degree ^[1][2] of a vertex of a graph is the number of edges that are incident to the vertex.

Definition

---

Definition 1 (Degree)

Let $G=(V,E)$ be a graph and $v\in V$ a vertex. The degree $\mathrm{deg}(v)$ of $v$ is

$$\mathrm{deg}(v):=|\{e\in E:v\in e\}|$$

the number of edges in $E$ ??incident?? to $v$.

Definition 2 (Maximum degree)

Let $G=(V,E)$ be a graph. The maximum degree of $G$ is

$$\Delta (G)=\underset{v\in V}{\max }\mathrm{deg}(v)$$

Definition 3 (Minimum degree)

Let $G=(V,E)$ be a graph. The minimum degree of $G$ is

$$\delta (G)=\underset{v\in V}{\min }\mathrm{deg}(v)$$

Notation

---

The degree of $v$ is denoted ${\mathrm{deg}}_G(v)$, or simply $\mathrm{deg}(v)$ when the graph is unambiguous. The maximum degree of $G$ is denoted $\Delta (G)$, and the minimum degree is denoted $\delta (G)$.

Properties

---

The sum of the degrees of all vertices of $G$ equals twice the number of edges, known as the handshaking lemma.

Multigraphs

---

Definition 1 extends to multigraphs, which allow parallel edges and loops, but a loop must be counted specially.

Definition 4 (Degree in a multigraph)

Let $G=(V,E,\psi )$ be a ??multigraph??, where $\psi :E\to \{\{u,v\}:u,v\in V\}$ maps each edge to its pair of endpoints, with $\psi (e)=\{v\}$ if $e$ is a ??loop?? at $v$. The degree of a vertex $v\in V$ is

$$\mathrm{deg}(v):=|\{e\in E:v\in \psi (e)\}|+|\{e\in E:\psi (e)=\{v\}\}|$$

the number of edges incident to $v$, with each loop at $v$ counted twice.

Since edges are distinct elements of $E$, two parallel edges with the same endpoints are counted separately by the first term even though $\psi$ sends them to the same pair. A loop is the exception to plain incidence counting. The second term adds one further count for each loop at $v$, so it contributes $2$ to $\mathrm{deg}(v)$ rather than the $1$ the first term alone would give.

Directed graphs

---

In a directed graph, the degree of a vertex $v$ splits into two directed notions. The in-degree ${\mathrm{deg}}^{-}(v)$ is the number of directed edges with $v$ as head, and the out-degree ${\mathrm{deg}}^{+}(v)$ is the number of directed edges with $v$ as tail.

Definition 5 (Degree in a directed graph)

Let $G=(V,E)$ be a directed graph and $v\in V$ a vertex. The degree of $v$ is

$$\mathrm{deg}(v):={\mathrm{deg}}^{-}(v)+{\mathrm{deg}}^{+}(v)$$

the sum of its in-degree and out-degree.

A self-loop $(v,v)\in E$ contributes $1$ to ${\mathrm{deg}}^{-}(v)$ and $1$ to ${\mathrm{deg}}^{+}(v)$, since $v$ serves as both its head and its tail, so it adds $2$ to $\mathrm{deg}(v)$ overall, matching the loop convention of Definition 4.

References

1. [1]

   “Degree (graph theory)”, Wikipedia, Available: https://en.wikipedia.org/wiki/Degree_(graph_theory), Accessed: 2026-07-31 ↩

2. [2]

   “Vertex Degree”, Wolfram MathWorld, Available: https://mathworld.wolfram.com/VertexDegree.html, Accessed: 2026-08-28 ↩