Vertex Degree — Definition, Formula & Examples

Vertex degree is the number of edges that connect to a given vertex in a graph. A self-loop counts as two toward the degree of its vertex.

For a vertex $v$ in an undirected graph $G = (V, E)$ , the degree of $v$ , denoted $\deg(v)$ , is the number of times $v$ appears as an endpoint of edges in $E$ . Each self-loop at $v$ contributes 2 to $\deg(v)$ , and every other incident edge contributes 1.

Key Formula

\sum_{v \in V} \deg(v) = 2|E|

Where:

$V$ = The set of all vertices in the graph
$E$ = The set of all edges in the graph
$\deg(v)$ = The degree of vertex v
$|E|$ = The total number of edges

How It Works

To find the degree of a vertex, count every edge attached to it. If the graph has no self-loops, this is simply the number of neighbors of that vertex. A vertex with degree 0 is called an isolated vertex, and a vertex with degree 1 is called a pendant (or leaf). The Handshaking Lemma states that the sum of all vertex degrees in a graph equals twice the number of edges, since each edge contributes exactly 1 to the degree of each of its two endpoints.

Worked Example

Problem: A graph has vertices A, B, C, D with edges {A–B, A–C, A–D, B–C, C–D}. Find the degree of each vertex and verify the Handshaking Lemma.

Count edges per vertex: List the edges touching each vertex. A appears in A–B, A–C, A–D. B appears in A–B, B–C. C appears in A–C, B–C, C–D. D appears in A–D, C–D.

\deg(A)=3,\; \deg(B)=2,\; \deg(C)=3,\; \deg(D)=2

Sum all degrees: Add the four degrees together.

3 + 2 + 3 + 2 = 10

Verify with Handshaking Lemma: The graph has 5 edges, so twice the number of edges is 10.

2|E| = 2(5) = 10 \;\checkmark

Answer: The degrees are 3, 2, 3, 2 and their sum equals

2 \times 5 = 10

, confirming the Handshaking Lemma.

Visualization

Why It Matters

Vertex degree is fundamental in network analysis — it measures how connected a node is in social networks, transportation grids, and computer networks. Degree sequences determine whether a graph can exist (via the Erdős–Gallai theorem) and drive algorithms for graph coloring, Eulerian paths, and matching.

Common Mistakes

Mistake: Counting a self-loop as degree 1 instead of degree 2.

Correction: A self-loop has both endpoints at the same vertex, so it contributes 2 to that vertex's degree. This preserves the Handshaking Lemma.