One of the simplest and, at the same time, most useful notions in graph theory is the degree of a vertex, that is, how many edges are connected to it. From this seemingly trivial definition emerges a central result of the field: the Handshaking Theorem.
Why Does the Degree of a Vertex Matter? #
The degree of a vertex is a simple local measure, yet it appears behind important results in mathematics and computing:
- Social networks: the degree of a vertex directly measures the number of connections of a person (or profile), the basis of centrality metrics and of “hub” detection in a network.
- Routing and infrastructure: in a computer or transportation network, the degree of a node indicates how many alternative routes pass through it, which is important information for analyzing robustness and single points of failure.
- Circuit and hardware design: the degree of a vertex in a connection graph limits the number of ports or physical pins needed at that point of the circuit.
- Structure checking: as we will see in the Handshaking Theorem, the sum of the degrees of a graph is always equal to twice the number of edges, a quick and cheap consistency check for any graph structure before running more costly algorithms on it.
Degree of a Vertex #
Let \(G = (V, E)\) be a graph and \(v \in V\). The degree of \(v\), denoted \(d(v)\) or \(d_G(v)\) (when more than one graph is in play), is the number of edges incident to \(v\), that is, the number of vertices adjacent to \(v\):
$$d(v) = |N(v)| = |\{w \in V \mid (v, w) \in E\}|$$In multigraphs with loops (edges from a vertex to itself), the usual convention is that a loop contributes 2 to the degree of the vertex, since the loop is incident twice to the vertex.
Example 1
Problem: Let \(G = (V, E)\) with
$$V = \{x,\ y,\ z,\ v,\ w,\ t,\ u\}$$$$E = \{(x,y),\ (y,z),\ (x,z),\ (x,w),\ (x,v),\ (z,v),\ (w,v),\ (z,t)\}$$
Compute the degree of each vertex of \(G\).
Solution: Counting the edges incident to each vertex:
- \(d(x) = 4\) (neighbors \(y, z, w, v\))
- \(d(y) = 2\) (neighbors \(x, z\))
- \(d(z) = 4\) (neighbors \(y, x, v, t\))
- \(d(v) = 3\) (neighbors \(x, z, w\))
- \(d(w) = 2\) (neighbors \(x, v\))
- \(d(t) = 1\) (neighbor \(z\))
- \(d(u) = 0\) (no neighbors: isolated vertex)
The figure below shows \(G\) with the degree of each vertex annotated. This is the graph we will reuse in the next examples.
Example 2
Problem: Let \(G\) be the multigraph with \(V = \{x, y, z, v, w\}\), in which there is a loop at vertex \(z\), two parallel edges between \(x\) and \(y\), and three between \(w\) and \(v\) (see the figure):
$$E = \{(x,y),\ (x,y),\ (y,z),\ (y,v),\ (x,v),\ (x,w),\ (z,v),\ (w,v),\ (w,v),\ (w,v),\ (z,z)\}$$Compute the degree of each vertex, remembering that the loop at \(z\) contributes 2 units.
Solution:
- \(d(x) = 4\)
- \(d(y) = 4\)
- \(d(z) = 4\) (includes the 2 units from the loop)
- \(d(v) = 6\)
- \(d(w) = 4\)
The next figure shows the multigraph with the parallel edges (in orange) and the loop at \(z\) highlighted.
Minimum Degree and Maximum Degree #
For a graph \(G\):
- \(\delta(G)\) = minimum degree = smallest degree among all the vertices of \(G\)
- \(\Delta(G)\) = maximum degree = largest degree among all the vertices of \(G\)
Example 3
Problem: Consider again the graph \(G\) from Example 1. Determine \(\delta(G)\) and \(\Delta(G)\).
Solution: The degrees computed in Example 1 were \(d(x)=4\), \(d(y)=2\), \(d(z)=4\), \(d(v)=3\), \(d(w)=2\), \(d(t)=1\), \(d(u)=0\). The smallest value is \(0\) (vertex \(u\)) and the largest is \(4\) (vertices \(x\) and \(z\)). Therefore:
$$\delta(G) = 0 \qquad \Delta(G) = 4$$The graph \(G\), with \(u\) (minimum degree) and \(x\), \(z\) (maximum degree) identifiable from the degree annotations.
Regular Graphs #
Some graphs have all vertices with the same degree: these are the regular graphs.
A graph \(G\) is called regular if all of its vertices have the same degree. In particular, if \(d(v) = k\) for every \(v \in V(G)\), we say that \(G\) is \(k\)-regular or regular of degree \(k\).
Example 4
Problem: Classify the graphs below by regularity.
- \(G_1\): three isolated vertices \(a, b, c\)
- \(G_2\): two pairs of vertices, each pair joined by one edge, \((x,y)\) and \((z,w)\)
- \(G_3\): a cycle of 4 vertices \(1\text{-}2\text{-}3\text{-}4\text{-}1\)
Solution:
- \(d(a) = d(b) = d(c) = 0\) → \(G_1\) is 0-regular
- \(d(x) = d(y) = d(z) = d(w) = 1\) → \(G_2\) is 1-regular
- \(d(1) = d(2) = d(3) = d(4) = 2\) → \(G_3\) is 2-regular
The three graphs are shown side by side below.
Example 4 (continued)
Problem: Also classify the graphs \(G_4\) (the cube graph, with 8 vertices), \(G_5 = K_4\), and \(G_6 = K_5\).
Solution:
- \(G_4\) (cube): every vertex has degree \(3\) → 3-regular
- \(G_5 = K_4\): every vertex has degree \(3\) → 3-regular
- \(G_6 = K_5\): every vertex has degree \(4\) → 4-regular
The three graphs are shown below: the cube \(G_4\), \(K_4\), and \(K_5\).
In general, \(K_n\) is regular of degree \(n-1\): each vertex is adjacent to all the other \(n-1\) vertices of the graph.
Sum of the Degrees of a Graph #
Before stating the general result, it is worth summing the degrees of two concrete graphs and observing the pattern that emerges.
Example 5
Problem: Sum the degrees of all the vertices of the graph \(G\) from Example 1.
Solution:
$$\sum_{v \in V} d(v) = d(x)+d(y)+d(z)+d(v)+d(w)+d(t)+d(u) = 4+2+4+3+2+1+0 = 16$$The graph \(G\) has exactly \(8\) edges, and \(16 = 2 \times 8\): the sum of the degrees is exactly twice the number of edges.
Example 6
Problem: Sum the degrees of all the vertices of the cube graph \(G_4\) (Example 4), which has 8 vertices, all of degree 3.
Solution:
$$\sum_{v \in V(G_4)} d(v) = 3 \times 8 = 24$$The graph \(G_4\) has exactly \(12\) edges, and again \(24 = 2 \times 12\).
The two examples above suggest a general pattern, which we formalize next.
The Handshaking Theorem #
The name of the following result comes from an analogy: if \(n\) people are in a room and each pair of people may or may not shake hands, the sum of the number of handshakes of each person is necessarily equal to twice the total number of handshakes (since each handshake is counted twice, once for each person involved).
For any graph \(G = (V, E)\):
$$\sum_{v \in V} d(v) = 2|E|$$Proof:
Each edge \((u, v) \in E\) contributes exactly 1 to \(d(u)\) and exactly 1 to \(d(v)\). Hence, each edge is counted exactly 2 times in the sum \(\sum_{v \in V} d(v)\). Therefore, \(\sum_{v \in V} d(v) = 2|E|\), which is what we wanted to prove. \(\blacksquare\)
The Handshaking Theorem also holds for multigraphs (using the convention that each loop contributes 2 units to the degree of the vertex).
In practice: the Handshaking Theorem on a real social network
Between 1970 and 1972, the anthropologist Wayne W. Zachary observed the social interactions of the 34 members of a university karate club and recorded, vertex by vertex, who interacted with whom outside of class. This dataset became known as Zachary’s Karate Club and became one of the most studied graphs in social network analysis.
During the study, a conflict between the karate instructor (nicknamed
“Mr. Hi”) and the club administrator (“John A.”) led to the split of the group:
half of the members formed a new club around Mr. Hi, and the rest
stayed with another instructor or gave up karate. The most remarkable part is that
Zachary managed to predict the split using only the structure of the graph: a
maximum-flow algorithm applied to the interaction network got the destination
of 33 of the 34 members right, missing only one (member 9 in Zachary’s numbering,
which goes from 1 to 34; in networkx, which numbers from 0, it is vertex 8),
whose actual choice differed from what the network structure suggested.
networkx already ships this graph, which lets us verify the Handshaking
Theorem on a real network (not just on examples with 7 or 8 vertices)
and use the degree to find the most influential members:
import networkx as nx
G = nx.karate_club_graph()
degrees = dict(G.degree())
degree_sum = sum(degrees.values())
num_edges = G.number_of_edges()
print(f"Sum of degrees: {degree_sum}")
print(f"2 x |E|: {2 * num_edges}")
print(f"Theorem verified: {degree_sum == 2 * num_edges}")
max_degree = max(degrees.values())
hubs = [v for v, d in degrees.items() if d == max_degree]
print(f"Highest-degree vertex(es): {hubs} (degree {max_degree})")Sum of degrees: 156
2 x |E|: 156
Theorem verified: True
Highest-degree vertex(es): [33] (degree 17)The theorem is confirmed even on a network with 34 vertices and 78 edges. And the
maximum-degree result is no coincidence: vertex 33 is exactly the
club administrator (club: "Officer"), and the runner-up, the
vertex 0 with degree 16, is the instructor (club: "Mr. Hi"), the two
poles around which the group split. The degree, a purely
local and easy-to-compute measure, already points to the two most central
figures in the network.
The figure below shows the complete graph, colored by the two factions
that resulted from the split, with the two hubs (vertices 0 and 33) highlighted by
a black outline.
Corollaries #
Corollary 1: The sum of the degrees of all the vertices of any graph is always an even number.
Proof: By the Handshaking Theorem, \(\sum_{v \in V} d(v) = 2|E|\), which is even by definition (a multiple of 2). Therefore, the sum of the degrees of any graph is always even, which is what we wanted to prove. \(\blacksquare\)
Corollary 2: In any graph, the number of vertices of odd degree is always even.
Proof: Split the vertices into two groups: \(V_{\text{even}}\) (even degree) and \(V_{\text{odd}}\) (odd degree). Then:
$$\sum_{v \in V_{\text{even}}} d(v) + \sum_{v \in V_{\text{odd}}} d(v) = 2|E|$$The first sum is even (a sum of even terms). Since the total \(2|E|\) is also even, the second sum (the sum of the odd degrees) must also be even. But a sum of odd numbers is even only when there is an even number of them. Therefore, the number of vertices of odd degree in any graph is always even, which is what we wanted to prove. \(\blacksquare\)
Corollary 3: In a \(k\)-regular graph with \(n\) vertices:
$$|E| = \frac{nk}{2}$$Proof: Let \(G\) be a \(k\)-regular graph with \(n\) vertices and \(m = |E|\). By the Handshaking Theorem:
$$\underbrace{k + k + \cdots + k}_{n \text{ terms}} = \sum_{v \in V} d(v) = 2m$$Hence \(nk = 2m\), that is, \(m = \dfrac{nk}{2}\). Therefore, every \(k\)-regular graph with \(n\) vertices has exactly \(\dfrac{nk}{2}\) edges, which is what we wanted to prove. \(\blacksquare\)
For a \(k\)-regular graph with \(n\) vertices to exist, \(nk\) must be even. In particular:
- If \(k\) is even, any \(n\) works
- If \(k\) is odd, \(n\) must be even
Applying Corollary 3
Question: Is there a 3-regular graph with 7 vertices?
If it existed, it would have \(|E| = 7 \times 3 / 2 = 10.5\) edges, which is impossible! Therefore, there is no 3-regular graph with 7 vertices.
Degree Sequence #
The degree sequence of a graph \(G\) with \(n\) vertices is the list of the degrees of all the vertices, in nondecreasing order (allowing repetitions when necessary):
$$(d_1, d_2, \ldots, d_n) \quad \text{with } d_1 \leq d_2 \leq \cdots \leq d_n$$
Example 7
Problem: Determine the degree sequence of the graph \(G\) from Example 1.
Solution: The degrees computed were \(d(u)=0\), \(d(t)=1\), \(d(y)=2\), \(d(w)=2\), \(d(v)=3\), \(d(x)=4\), \(d(z)=4\). Sorting in nondecreasing order:
$$(0,\ 1,\ 2,\ 2,\ 3,\ 4,\ 4)$$
Example 8
Problem: Determine the degree sequence of the cube graph \(G_4\).
Solution: All 8 vertices have degree 3, so the degree sequence is:
$$(3,\ 3,\ 3,\ 3,\ 3,\ 3,\ 3,\ 3)$$
Exercises #
The following exercises apply the Handshaking Theorem and its corollaries in different contexts.
Exercise 1: Number of vertices of odd degree
Problem: At a party with 30 people, each person shook hands with a specific number of other people. Prove that the number of people who shook hands an odd number of times is even.
Solution
Model the party as a graph: people are vertices, handshakes are edges. By Corollary 2 of the Handshaking Theorem, the number of vertices of odd degree is always even. Therefore, the number of people who shook hands an odd number of times is even, which is what we wanted to prove. \(\blacksquare\)
Exercise 2: Pigeonhole principle for degrees
Problem: Prove that in any simple graph with \(n \geq 2\) vertices, there are at least two vertices with the same degree.
Solution
The possible degrees in a simple graph with \(n\) vertices are \(0, 1, 2, \ldots, n-1\), that is, \(n\) possible values for \(n\) vertices. However, the values \(0\) and \(n-1\) cannot occur simultaneously: an isolated vertex (degree \(0\)) cannot coexist with a universal vertex (degree \(n-1\)), since the universal vertex would be adjacent to the isolated one, which is a contradiction. Hence, there are at most \(n-1\) distinct degree values available for \(n\) vertices. By the pigeonhole principle, at least two vertices must share the same degree. Therefore, every simple graph with \(n \geq 2\) vertices has two vertices of the same degree, which is what we wanted to prove. \(\blacksquare\)
Summary #
The following table summarizes the main concepts and results presented in this article.
| Concept | Notation | Description |
|---|---|---|
| Degree of \(v\) | \(d(v)\), \(d_G(v)\) | Number of edges incident to \(v\) |
| Minimum degree | \(\delta(G)\) | Smallest degree in the graph |
| Maximum degree | \(\Delta(G)\) | Largest degree in the graph |
| \(k\)-regular graph | - | Every vertex has degree \(k\) |
| Handshaking Theorem | \(\sum d(v) = 2|E|\) | Sum of degrees = twice the number of edges |
| Corollary 1 | - | Sum of the degrees of any graph is even |
| Corollary 2 | - | Number of vertices of odd degree is even |
| Corollary 3 | \(|E| = \dfrac{nk}{2}\) | Edges of a \(k\)-regular graph with \(n\) vertices |
| Degree sequence | \((d_1, \ldots, d_n)\) | Degrees listed in nondecreasing order |
Next Steps #
The degree of each vertex and the degree sequence of a graph are useful tools, but they have a clear limit: two graphs can have exactly the same degree sequence and still be completely different structures, or, conversely, look different only because their vertices were labeled differently, when in fact they have the same structure. We lack tools to answer the question “are these two graphs essentially the same graph?”. This is the question that motivates graph isomorphism, the topic of the next article in the series, where we will also see how to represent graphs by adjacency and incidence matrices.
