Handshaking Lemma and Corollary

Handshaking Lemma and Corollary

The Handshaking Lemma is a fundamental result in graph theory that relates the degree of the vertices in a graph to the number of edges. It provides insights into the structure of a graph and is often used in combinatorial proofs.

---

1. Handshaking Lemma (Theorem)

The Handshaking Lemma states that in any undirected graph, the sum of the degrees of all the vertices is twice the number of edges.

Formal Statement:

For a graph $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges:

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

Where:

• $\text{deg}(v)$ is the degree of vertex $v$, which is the number of edges incident to $v$.
• $|E|$ is the total number of edges in the graph.

Explanation:

Each edge in an undirected graph connects two vertices and contributes 1 to the degree of both of those vertices. Therefore, for each edge, it "adds" 1 to the degree of two vertices. This means that the sum of the degrees of all vertices counts each edge twice. Thus, the total degree of all vertices is twice the number of edges.

---

2. Proof of the Handshaking Lemma

To prove the Handshaking Lemma, consider the following steps:

1. Counting the edges: Each edge in the graph connects two vertices, and so each edge is counted once for each of the two vertices it connects.
2. Degree of vertices: The degree of a vertex $v$, $\text{deg}(v)$, is the number of edges incident to $v$. When we sum the degrees of all vertices, we are counting the total number of edge incidences across the graph (i.e., how many times an edge is incident to a vertex).
3. Counting twice: Since each edge is counted twice—once for each of its two endpoints—the sum of the degrees of all vertices is twice the number of edges.

Thus, we can conclude that:

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

---

3. Corollary of the Handshaking Lemma

From the Handshaking Lemma, we can derive some important corollaries:

Corollary 1: The number of vertices with odd degree is even.

Statement: In any undirected graph, the number of vertices with an odd degree is always even.

Proof:

• The Handshaking Lemma states that the sum of all vertex degrees is even (since it is twice the number of edges).
• If there are an odd number of vertices with odd degrees, then the sum of their degrees would be odd, which would contradict the Handshaking Lemma.
• Therefore, the number of vertices with odd degree must be even.

Example: In a graph, if there are 3 vertices with an odd degree, the total degree sum would be odd, which is not possible since the sum must be even. Hence, there must always be an even number of vertices with an odd degree.

---

Corollary 2: A graph with no edges has all vertex degrees equal to zero.

Statement: In a graph with no edges, every vertex has degree 0.

Proof:

• If a graph has no edges, then there are no connections between vertices.
• Thus, each vertex is isolated, meaning that it has 0 edges incident to it.
• The sum of degrees of all vertices in the graph is zero, which satisfies the Handshaking Lemma (since the number of edges $|E| = 0$, the sum of degrees is $2 \times 0 = 0$).

---

4. Practical Implications and Applications of the Handshaking Lemma

The Handshaking Lemma provides insight into the structure and properties of a graph. It has applications in several areas:

1. Degree Constraints: The lemma gives us a quick way to check whether certain degree conditions can be satisfied in a graph. For example, in a graph where each vertex has degree 3, the total number of vertices must be even (since the sum of degrees will be $3n$, which must be even).

2. Network Design: In the design of communication or transportation networks (where vertices represent stations and edges represent direct connections), the lemma helps analyze the number of connections required.

3. Graph Coloring and Matching: The lemma can also play a role in algorithms related to graph coloring or matching, as it offers a basic understanding of how edges and vertices are connected in a graph.

---

5. Example of the Handshaking Lemma

Consider a simple undirected graph:

    A --- B
    |     |
    C --- D

• Vertices: $A, B, C, D$
• Edges: $\{ (A, B), (A, C), (B, D), (C, D) \}$

The degrees of the vertices are:

• $\text{deg}(A) = 2$
• $\text{deg}(B) = 2$
• $\text{deg}(C) = 2$
• $\text{deg}(D) = 2$

Sum of degrees:

$$\text{deg}(A) + \text{deg}(B) + \text{deg}(C) + \text{deg}(D) = 2 + 2 + 2 + 2 = 8$$

Number of edges:

$$|E| = 4$$

According to the Handshaking Lemma:

$$\sum_{v \in V} \text{deg}(v) = 2|E| = 2 \times 4 = 8$$

This verifies the Handshaking Lemma.

---

Summary

• Handshaking Lemma: The sum of the degrees of all vertices in an undirected graph is equal to twice the number of edges.
• Corollary 1: The number of vertices with odd degree in any undirected graph is always even.
• Corollary 2: A graph with no edges has all vertex degrees equal to zero.
• The Handshaking Lemma is useful for understanding basic properties of graphs, especially in terms of vertex degrees and edge connections. It also plays a crucial role in proofs and algorithmic applications related to graphs.