Graph theory provides a simple way to represent relationships between objects. A graph consists of vertices, which represent objects, and edges, which represent connections between those objects. Once the basic idea of vertices and edges is understood, one of the most important concepts to learn is the degree of a vertex.
The degree of a vertex tells us how many edges are connected to that vertex. This seemingly simple idea is extremely useful because it allows us to study the structure of a graph without examining every connection individually. Degree can help us identify highly connected vertices, isolated vertices, paths, cycles, and many other structural properties.
Another closely related idea is edge counting. By examining the degrees of all vertices, we can determine the total number of edges in an undirected graph. This relationship is known as the Handshaking Lemma.
In this article, we will learn what the degree of a vertex means, how to calculate it, how loops affect degree, how degrees are used to count edges, and how these concepts help us understand graphs.
What Is the Degree of a Vertex?
The degree of a vertex is the number of edges that are incident to that vertex.
In simple terms, it tells us how many connections a vertex has.
For example, suppose a graph has a vertex named A. If three different edges connect to A, then the degree of A is 3.
The degree is commonly written as deg(A).
Example
Consider a graph containing the vertices A, B, C, and D. Suppose A is connected to B, C, and D.
There are three edges incident to A:
A–B
A–C
A–D
Therefore, the degree of A is 3.
Text block:
deg(A) = 3
The degree does not depend on the names of the other vertices. It simply counts how many edges touch the vertex.
Understanding Incident Edges
Before calculating degree, it is useful to understand the word incident.
An edge is said to be incident to a vertex if the edge has that vertex as one of its endpoints.
For example, if an edge connects A and B, written as A–B, then the edge is incident to both A and B.
Therefore:
A–B contributes 1 to the degree of A.
A–B also contributes 1 to the degree of B.
This is why counting the degrees of vertices provides information about the edges in an undirected graph.
Degree in a Simple Graph
A simple graph is an undirected graph with no loops and no multiple edges between the same pair of vertices.
In a simple graph, every edge connecting two different vertices contributes one to the degree of each endpoint.
For example, consider the edges:
A–B
A–C
B–C
C–D
The degrees are:
A has degree 2.
B has degree 2.
C has degree 3.
D has degree 1.
We can represent this as a degree sequence:
Text block:
2, 2, 3, 1
The order of the degrees usually follows the order in which the vertices are listed.
Degree of an Isolated Vertex
An isolated vertex is a vertex that has no edges connected to it.
Since there are no incident edges, its degree is zero.
Text block:
deg(v) = 0
For example, if a graph contains vertices A, B, C, and D, and D is not connected to any other vertex, then D is isolated.
Text block:
deg(D) = 0
Isolated vertices are important because they contribute nothing to the edge count.
Degree of a Leaf or Pendant Vertex
A vertex with degree 1 is often called a leaf or pendant vertex.
It has exactly one edge connected to it.
For example, if vertex D is connected only to C, then:
Text block:
deg(D) = 1
Leaf vertices commonly appear at the ends of trees and other network structures.
Degree of a Vertex with Several Connections
A vertex can have any number of connections permitted by the graph.
Suppose vertex P is connected to Q, R, S, T, and U. Five edges are incident to P.
Therefore:
Text block:
deg(P) = 5
The degree provides a quick measure of how strongly a vertex is connected to the rest of the graph.
In applications, a vertex with a high degree may represent a highly connected person in a social network, an important computer in a communication network, or a major intersection in a transportation network.
How a Loop Affects Degree
A loop is an edge that begins and ends at the same vertex.
For example, an edge may start at A and return to A.
A loop contributes 2 to the degree of the vertex because the loop touches the vertex at both ends.
Therefore, if a vertex has two ordinary edges and one loop, its degree is:
Text block:
deg(A) = 1 + 1 + 2
This is an important rule to remember:
In an undirected graph, each loop contributes 2 to the degree of its vertex.
Students sometimes count a loop as only one edge when calculating degree. Although it is one edge, it contributes two to the degree.
Degree Sequence
The list of degrees of all vertices in a graph is called the degree sequence.
Suppose a graph has five vertices with degrees:
A = 2
B = 3
C = 1
D = 2
E = 4
The degree sequence can be written as:
Text block:
2, 3, 1, 2, 4
The degree sequence provides a compact description of the connectivity of a graph.
It can also be arranged from largest to smallest:
Text block:
4, 3, 2, 2, 1
Degree sequences are useful when comparing graphs or determining whether a proposed collection of degrees can belong to a graph.
Counting Edges Using Vertex Degrees
One of the most useful results in graph theory is the Handshaking Lemma.
It states that in every finite undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges.
This happens because every edge has two endpoints. When we add the degrees of all vertices, every edge is counted once at each endpoint.
Text block:
Sum of degrees = 2 × Number of edges
If E represents the number of edges, the relationship can be written as:
Text block:
E = (Sum of all vertex degrees) / 2
This formula allows us to find the number of edges without listing every edge individually.
Example of Edge Counting
Suppose a graph has six vertices with the following degrees:
Text block:
2, 3, 2, 4, 1, 2
First, add the degrees:
Text block:
2 + 3 + 2 + 4 + 1 + 2 = 14
The sum of the degrees is 14.
According to the Handshaking Lemma, this must equal twice the number of edges.
Therefore:
Text block:
2E = 14
So:
Text block:
E = 7
The graph has 7 edges.
Why Does the Handshaking Lemma Work?
The easiest way to understand the Handshaking Lemma is to imagine people shaking hands.
Suppose several people are standing in a room. Every handshake involves exactly two people.
If we count the number of handshakes made by each person and then add all those numbers together, every handshake will have been counted twice: once for each person involved.
The same idea applies to an undirected graph.
Every edge connects two endpoints. Therefore, when we add the degrees of all vertices, every edge is counted exactly twice.
That is why:
Text block:
Sum of degrees = 2 × Number of edges
This idea gives the Handshaking Lemma its name.
The Sum of Degrees Is Always Even
An important consequence of the Handshaking Lemma is that the sum of the degrees of all vertices in an undirected graph must always be even.
Why?
Because the sum is equal to twice the number of edges.
Since twice any whole number is even, the degree sum must also be even.
For example:
Text block:
2 + 3 + 1 + 4 = 10
The sum is even, so it could represent the degree sum of an undirected graph.
But consider:
Text block:
2 + 2 + 3 = 7
The sum is odd. Therefore, these three numbers cannot be the complete degree sequence of an undirected graph.
This provides a quick way to reject impossible degree sequences.
Counting Edges from a Regular Graph
A graph is called regular when every vertex has the same degree.
Suppose a graph has n vertices and every vertex has degree r.
The total degree is therefore:
Text block:
Total degree = n × r
Using the Handshaking Lemma:
Text block:
n × r = 2E
Therefore:
Text block:
E = nr / 2
For example, suppose a graph has 8 vertices and every vertex has degree 3.
Text block:
E = (8 × 3) / 2
Therefore, the graph has 12 edges.
Maximum Degree in a Simple Graph
In a simple graph with n vertices, a vertex cannot be connected to itself because loops are not allowed. It also cannot have multiple edges connecting it to the same vertex.
Therefore, a vertex can connect to at most every other vertex.
The maximum possible degree is:
Text block:
Maximum degree = n − 1
For example, in a simple graph with 7 vertices, the maximum degree of any vertex is:
Text block:
7 − 1 = 6
A vertex can be connected to the other six vertices, but not to itself.
Minimum and Maximum Number of Edges
For a simple graph with n vertices, the minimum number of edges is 0. This occurs when every vertex is isolated.
Text block:
Minimum number of edges = 0
The maximum number of edges occurs when every pair of distinct vertices is connected. Such a graph is called a complete graph.
The maximum number of edges is:
Text block:
Maximum number of edges = n(n − 1) / 2
For example, a simple graph with 5 vertices can have at most:
Text block:
5(5 − 1) / 2
So the maximum number of edges is 10.
Degree in Directed Graphs
Degree is slightly different in a directed graph because edges have directions.
A directed graph has:
Indegree — the number of edges entering a vertex.
Outdegree — the number of edges leaving a vertex.
For example, suppose three directed edges enter vertex A and two directed edges leave A.
Then:
Text block:
Indegree(A) = 3
The total directed degree is sometimes considered as the sum of indegree and outdegree:
Text block:
Total degree = Indegree + Outdegree
For this example:
Text block:
Total degree = 3 + 2
In a directed graph, the sum of all indegrees equals the number of directed edges, and the sum of all outdegrees also equals the number of directed edges.
Practical Importance of Vertex Degree
Vertex degree is not just a theoretical idea. It is useful in many real-world systems.
In a social network, a person with many direct connections has a high degree.
In a computer network, a device connected to many other devices has a high degree.
In a transportation network, an intersection connected to many roads has a high degree.
In a web network, a page connected to many other pages can be represented by a vertex with a larger degree.
In these situations, degree helps researchers identify highly connected or important points in a network.
Common Mistakes When Finding Degree
There are several mistakes that students commonly make.
Counting vertices instead of edges
The degree of a vertex is based on the number of incident edges, not simply the number of vertices nearby.
Forgetting that a loop contributes 2
A loop is one edge, but it contributes two to the degree of its vertex.
Forgetting to count every incident edge
When a vertex has many connections, it is easy to overlook one edge. Carefully trace each edge that touches the vertex.
Confusing degree with the total number of graph edges
The degree belongs to an individual vertex. The number of edges belongs to the entire graph.
For example, a graph may have 10 edges while one particular vertex has degree 4.
A Quick Method for Solving Degree and Edge Problems
When solving problems involving vertex degree and edge counting, follow these steps:
Identify all the vertices in the graph.
Choose the vertex whose degree is required.
Count every edge incident to that vertex.
If there is a loop, count it as 2 toward the degree.
If the degrees of all vertices are given, add them together.
Use the Handshaking Lemma to determine the number of edges.
Check that the total degree is even for an undirected graph.
This method works for many basic graph theory problems.
Conclusion
The degree of a vertex is one of the fundamental concepts in graph theory. It tells us how many edges are incident to a vertex and gives a simple way to describe the connectivity of a graph.
The concept becomes especially powerful when the degrees of all vertices are considered together. The Handshaking Lemma establishes that the sum of the degrees in an undirected graph is twice the number of edges. This makes it possible to calculate the number of edges from vertex degrees and also explains why the total degree must always be even.
Understanding vertex degree, degree sequences, loops, regular graphs, and edge counting provides an important foundation for studying more advanced topics in graph theory. These ideas are also useful in practical network problems involving social connections, computer systems, transportation networks, and many other structures.
FAQs
1. What is the degree of a vertex in a graph?
The degree of a vertex is the number of edges incident to that vertex. In simple terms, it tells us how many direct connections a vertex has with other vertices. For example, if vertex A is connected to B, C, and D, then A has three incident edges, so its degree is 3. The degree is commonly written as deg(A). In an undirected graph, each ordinary edge contributes one to the degree of each endpoint. Degree is an important concept because it helps describe the structure and connectivity of a graph and is widely used in network analysis and graph theory.
2. How do you calculate the degree of a vertex?
To calculate the degree of a vertex, count all the edges that are incident to that vertex. Each ordinary edge connected to the vertex contributes one to its degree. For example, if vertex P is connected to Q, R, S, and T, then four edges touch P, so the degree of P is 4. If the graph contains a loop at P, that loop contributes two to the degree because it touches P at both ends. Therefore, when calculating degree, carefully count every incident edge and remember the special rule for loops in an undirected graph.
3. What is the Handshaking Lemma in graph theory?
The Handshaking Lemma states that the sum of the degrees of all vertices in a finite undirected graph is equal to twice the number of edges. This happens because every edge has two endpoints. When the degrees of all vertices are added, every edge is counted once at each endpoint. Therefore, the total degree is always twice the number of edges. This relationship is useful for calculating the number of edges when vertex degrees are known. It also provides an important check: the sum of all vertex degrees in an undirected graph must always be an even number.
4. How can vertex degrees be used to count edges?
Vertex degrees can be used to find the number of edges by adding the degrees of all vertices and dividing the result by 2. This follows directly from the Handshaking Lemma. For example, if the degrees of four vertices are 2, 3, 2, and 3, their total degree is 10. Since every edge contributes two to the total degree, the graph contains 10 divided by 2, or 5 edges. This method is particularly useful when a graph contains many vertices and it is easier to work with their degrees than to count individual edges.
5. Why is the sum of vertex degrees always even?
In an undirected graph, every edge connects exactly two endpoints. When the degrees of all vertices are added, each edge is counted twice, once for each endpoint. Therefore, the total degree is always twice the number of edges. Since twice any whole number is even, the sum of all vertex degrees must also be even. For example, if a graph contains 8 edges, the sum of its vertex degrees must be 16. This property is useful for checking whether a proposed degree sequence could belong to an undirected graph. An odd total degree indicates that the sequence is impossible.
6. How does a loop affect the degree of a vertex?
A loop is an edge that starts and ends at the same vertex. In an undirected graph, a loop contributes 2 to the degree of that vertex. This is because the edge has two endpoints, and both endpoints are the same vertex. For example, suppose vertex A has two ordinary edges connected to other vertices and one loop. The two ordinary edges contribute 2, while the loop contributes another 2. Therefore, the degree of A is 4. It is important not to count a loop as only one when calculating vertex degree, even though the loop itself is one edge.
7. What is a degree sequence in graph theory?
A degree sequence is a list containing the degrees of all vertices in a graph. It provides a compact way to describe how connections are distributed among the vertices. For example, if a graph has five vertices with degrees 4, 3, 2, 2, and 1, its degree sequence is 4, 3, 2, 2, 1. Degree sequences can be written in any vertex order or arranged from largest to smallest. They are useful for studying graph structure and determining whether a particular collection of numbers can represent the degrees of vertices in a valid graph.
8. What is the maximum degree of a vertex in a simple graph?
In a simple graph containing n vertices, the maximum possible degree of any vertex is n − 1. This is because a vertex cannot have a loop and cannot have multiple edges connecting it to the same vertex. Therefore, it can be connected to every other vertex, but not to itself. For example, if a simple graph has 8 vertices, one vertex can be connected to the other 7 vertices. Its maximum possible degree is therefore 7. This rule is useful when checking whether a proposed degree is possible in a simple graph.
9. How many edges can a simple graph with n vertices have?
A simple graph with n vertices can have a maximum of n(n − 1)/2 edges. The maximum occurs when every pair of distinct vertices is connected by exactly one edge. Such a graph is called a complete graph. For example, a simple graph with 5 vertices can have a maximum of 5(5 − 1)/2 = 10 edges. The minimum number of edges is 0, which occurs when all vertices are isolated. Therefore, the number of edges in a simple graph can range from zero to the maximum determined by the number of vertices.
10. What is the difference between degree and number of edges?
The degree describes the number of edges connected to a particular vertex, while the number of edges describes the total number of connections in the entire graph. For example, a graph may contain 10 edges, but a particular vertex may have a degree of only 3. In an undirected graph, the degrees of all vertices are related to the total number of edges through the Handshaking Lemma. Specifically, the sum of all vertex degrees equals twice the number of edges. Therefore, degree is a local property of a vertex, while the total edge count is a property of the whole graph.
