The degree of a vertex is the number of edges connected to it. Written as deg(v), it’s one of the most fundamental measurements in graph theory and the starting point for understanding how graphs behave. If a vertex has three edges touching it, its degree is 3.
How Vertex Degree Works
A graph is a collection of vertices (points) connected by edges (lines). The degree of any vertex is simply a count of how many edges meet at that point. Picture five people in a room, each represented by a dot. Draw a line between any two people who know each other. If one person knows three others, their vertex has degree 3.
Two special cases come up often. A vertex with degree 0, meaning no edges touch it at all, is called an isolated vertex. A vertex with degree 1, connected by a single edge, is called a pendant vertex. These terms appear frequently in proofs and problem sets because they represent boundary conditions in a graph’s structure.
Degree in Directed Graphs
In a standard (undirected) graph, edges have no direction. But in a directed graph, each edge goes from one vertex to another, like a one-way street. This splits the concept of degree into two parts:
- In-degree, written deg⁻(v), counts the number of edges pointing into a vertex.
- Out-degree, written deg⁺(v), counts the number of edges pointing out from a vertex.
If you think of a Twitter-style social network where “following” is one-directional, in-degree represents how many followers someone has, while out-degree represents how many people they follow. The two numbers can be completely different for the same vertex.
The Handshaking Lemma
One of the first theorems students encounter in graph theory ties vertex degrees directly to the number of edges. The degree sum formula (often called the handshaking lemma) states that if you add up the degrees of every vertex in a graph, the result is exactly twice the number of edges. In notation: the sum of deg(v) for all vertices equals 2|E|, where |E| is the total edge count.
This makes intuitive sense. Every edge has two endpoints, so each edge contributes 1 to the degree of each endpoint, adding 2 to the total sum. A practical consequence: the sum of all vertex degrees in any graph is always an even number, which means the number of vertices with odd degree is always even. This simple fact turns out to be surprisingly powerful for proving whether certain graphs can exist.
Minimum and Maximum Degree
When analyzing a whole graph rather than a single vertex, two summary values come up constantly. The minimum degree, written with the Greek letter δ(G), is the smallest degree found among all vertices. The maximum degree, written Δ(G), is the largest. A graph where every vertex has degree between 3 and 5, for example, has δ(G) = 3 and Δ(G) = 5.
When every vertex in a graph has the same degree, the graph is called regular. More specifically, a graph where every vertex has degree k is called k-regular. A cube, for instance, is 3-regular because every corner connects to exactly three edges. Regular graphs show up throughout combinatorics and network design because their uniformity makes them easier to analyze and often gives them desirable properties like symmetry and balanced connectivity.
Degree Sequences
List out the degree of every vertex in a graph and sort the numbers in non-increasing order. That list is the graph’s degree sequence. For a triangle (three vertices, each connected to the other two), the degree sequence is [2, 2, 2]. For a path of four vertices connected in a line, it’s [2, 2, 1, 1].
A natural question arises: given a list of numbers, can you always build a graph with that degree sequence? Not necessarily. A sequence of non-negative integers that can be realized as the degrees of some simple graph is called a graphic sequence. The Havel-Hakimi algorithm provides a systematic way to check. It works by repeatedly taking the largest degree in the sequence, “connecting” it to the next entries by subtracting 1 from that many values, removing it, re-sorting, and repeating. If you ever reach all zeros, the sequence is graphic. If you hit a negative number or an impossible state, no such graph exists.
For example, consider the sequence [3, 3, 2, 2, 2]. Take the first value (3), subtract 1 from the next three values, giving [2, 1, 1, 2]. Re-sort to [2, 2, 1, 1], then repeat. This process eventually reduces to all zeros, confirming a graph with that degree sequence can be drawn.
Degree Centrality in Networks
Outside pure mathematics, vertex degree becomes a practical tool for measuring importance in networks. In network science, the degree of a vertex is the simplest form of centrality: the idea that the more connections a node has, the more influential it is. A person in a social network who knows 200 people has higher degree centrality than someone who knows 10, and is better positioned to spread information quickly.
This concept extends beyond individual vertices. Researchers also measure degree centrality for clusters, counting how many outside vertices connect to at least one member of the group. A tightly connected group (called a clique) with high degree centrality represents a cohesive cluster that also reaches many people beyond its boundaries. This makes degree centrality useful in fields ranging from biology to tourism management to automated text summarization, anywhere you need to identify the most connected or influential nodes in a system.
Degree centrality’s main advantage is simplicity. It requires nothing more than counting edges, which makes it fast to compute even in networks with millions of nodes. More sophisticated measures like betweenness centrality and closeness centrality capture different aspects of a node’s position, but degree remains the most intuitive starting point for understanding network structure.