Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 2

Understanding Degrees and the Handshaking Lemma

Recommended resources

Introduction

In our last lesson, we established the foundational vocabulary for graph theory, defining what a graph is and classifying graphs based on directionality and edge weights. Now that you can identify and describe different types of graphs, we will move on to quantifying their properties. This lesson focuses on the characteristics of individual vertices.

We will define the degree of a vertex, which is a simple count of its connections. For directed graphs, we will refine this concept into in-degree and out-degree to account for the direction of edges. We will then explore the Handshaking Lemma, a fundamental theorem that reveals a surprising and powerful relationship between the degrees of all vertices and the total number of edges in a graph. Mastering these concepts is essential, as they form the basis for many algorithms and problem-solving techniques in competitive programming.

Degree of a Vertex in Undirected Graphs

In an undirected graph, the connections are mutual. The simplest way to measure the "busyness" or connectivity of a vertex is to count how many edges are attached to it. This measure is called the degree.

[PDF] v1 v2 v v4 e1 e2 e3 e4 - FSU Math

This document from Florida State University provides concise, formal definitions that align with your preference for theoretical rigor.

Please read section 2.1, "Undirected Graphs." Focus on the definition of degree, denoted as \deg(v). Pay close attention to the special rule: a loop (an edge from a vertex to itself) contributes twice to the degree. This is a crucial detail because a loop involves the vertex as an endpoint twice. Also, note the definitions for an isolated and pendant vertex.

To summarize the key points:

  • Degree of a vertex , : The number of edges incident to .
  • A loop at vertex adds 2 to .
  • Isolated vertex: A vertex with a degree of 0.
  • Pendant vertex: A vertex with a degree of 1.

The Handshaking Lemma

One of the first, most elegant, and surprisingly useful theorems in graph theory is the Handshaking Lemma. It establishes a direct link between the local property of vertex degrees and the global property of the total number of edges.

The intuition is straightforward: every edge has exactly two endpoints. If you were to go to each vertex and count its incident edges, then sum these counts, you would have counted every edge in the graph exactly twice.

The Handshake Lemma

This short video from Mathispower4u provides an excellent explanation of the Handshaking Lemma, its applications, and an important corollary.

Please watch the entire video. Pay attention to the following: The formal statement of the lemma. An example of how to use the lemma to find the number of edges given a graph's degree sequence. The key implication: the sum of degrees must be even. This is used to determine if a graph with certain properties can even exist. The final proposition: any graph must have an even number of vertices with an odd degree. This is a classic result often used in proofs and problem-solving.

To solidify this with a formal proof, let's turn back to the FSU document.

[PDF] v1 v2 v v4 e1 e2 e3 e4 - FSU Math

This section provides the formal theorem and its proof, which is beautifully simple.

Read section 2.2, "The Handshaking Theorem." Focus on the theorem statement and its concise proof. The formula is: \sum_{v \in V} \deg(v) = 2|E| where |E| is the number of edges. Also, read the following section, which discusses the important corollary that every graph has an even number of vertices of odd degree and provides its proof.

This theorem is more than a mathematical curiosity. In competitive programming, it can help you quickly validate or invalidate assumptions about a graph's structure in an ad-hoc problem. For example, if a problem describes a scenario that translates to a graph with an odd number of odd-degree vertices, you know immediately that such a scenario is impossible.

In-Degree and Out-Degree in Directed Graphs

In directed graphs, an edge represents a one-way connection from to . Simply counting the edges incident to a vertex isn't enough; we need to know whether the edges are arriving at the vertex or leaving from it. This leads to two new concepts: in-degree and out-degree.

This image provides clear definitions for in-degree and out-degree. For each vertex in the example graph G, verify the calculated values. For instance, vertex 'a' has two incoming edges (from 'e' and a loop on itself) and four outgoing edges (to 'b', 'c', 'e', and a loop on itself).

Let's formalize these definitions.

[PDF] v1 v2 v v4 e1 e2 e3 e4 - FSU Math

This document defines in-degree and out-degree and presents the corresponding version of the Handshaking Lemma for directed graphs.

First, read section 2.4, "Directed Graphs." This section provides the formal definitions for in-degree, denoted \deg^-(v), and out-degree, denoted \deg^+(v). Next, read section 2.5, "The Handshaking Theorem for Directed Graphs." Notice the formula here is different but just as intuitive. Each edge contributes exactly 1 to the total sum of in-degrees and exactly 1 to the total sum of out-degrees.

This leads to the Handshaking Lemma for directed graphs:

This means the sum of all in-degrees equals the sum of all out-degrees, and both are equal to the total number of edges.

Calculating In-Degree and Out-Degree in Code

In competitive programming, you'll often work with a graph represented by an adjacency list. Calculating degrees from this representation is a common and straightforward task. Since you are comfortable with C++, let's see how this is done.

Find Indegree and Outdegree for all vertices - GeeksforGeeks

This GeeksforGeeks article provides a clear, practical approach to calculating in-degrees and out-degrees from an adjacency list, which is a very common task in competitive programming.

Read the Approach section. The logic is simple: Initialize inDegree and outDegree arrays of size V to all zeros. Iterate through each vertex u from 0 to V-1. The out-degree of u is simply the size of its adjacency list (adj[u].size()). For each neighbor v in adj[u], you increment the in-degree of v (inDegree[v]++). After reading the approach, examine the C++ code implementation in the section just below it. This function perfectly demonstrates the algorithm described. Understanding this code snippet is a great first step toward working with graphs programmatically.

The concept of in-degree is particularly vital for algorithms like topological sorting, which we will cover later in this course. A vertex with an in-degree of 0 is a starting point—it has no dependencies.

Conclusion

In this lesson, we added quantitative measures to our understanding of graphs. You've learned how to describe the connectivity of any vertex using the concepts of degree, in-degree, and out-degree. We also explored the Handshaking Lemma in both its undirected and directed forms, establishing a fundamental relationship between vertex degrees and the total number of edges.

Key Takeaways:

  • Degree : In an undirected graph, the number of edges incident to vertex . Loops count twice.
  • In-Degree : In a directed graph, the number of edges that terminate at vertex .
  • Out-Degree : In a directed graph, the number of edges that originate from vertex .
  • Handshaking Lemma (Undirected): The sum of all degrees is twice the number of edges: . An important consequence is that the number of odd-degree vertices must be even.
  • Handshaking Lemma (Directed): The sum of in-degrees equals the sum of out-degrees, which equals the number of edges: .

Now that we have covered some basic properties, our next step is to define how we move around a graph. In the next lesson, we will introduce the concepts of paths, cycles, and connected components, which are essential for understanding graph traversal and connectivity.