Handshake Lemma

A simple breakdown

The Handshake Lemma is a fundamental idea in graph theory that connects vertices and edges in a very simple way.

If you’d like a formal definition see

---

The Big Idea

Every edge in a graph connects two vertices.

Because of this, every edge contributes 2 to the total degree count:

• one for each vertex it touches

The Rule

\(\text{Sum of all vertex degrees} = 2 \times (\text{number of edges}) \)

Why is it called the Handshake Lemma?

Imagine a group of people shaking hands.

• Each handshake involves two people

• If you count how many handshakes each person has participated in and add them up,
  you will count every handshake twice

👉 Graphs work the same way:

• vertices = people

• edges = handshakes

Example

Suppose you have the following graph

      A
     / \
    B   C
   / \
  D   E

Degrees of Each Vertex

• A → connected to B, C → degree = 2

• B → connected to A, D, E → degree = 3

• C → connected to A → degree = 1

• D → connected to B → degree = 1

• E → connected to B → degree = 1

\(2+3+1+1+1=8\)

Or, much more intuitively, we can count the edges:

• A—B

• A—C

• B—D

• B—E

Then use the handshake lemma:

\(8 = 2 \times \text{edges} \Rightarrow \text{edges} = 4\)

For simple math…

For trees, we already know:

\(\text{edges} = n - 1\)

So:

\(\text{total degree} = 2(n - 1)\)

This helps us quickly verify whether a structure could be a valid tree.

Important Insight

The sum of all vertex degrees must always be even

Why?

\(2 \times (\text{number of edges}) = \text{even number}\)

So if the total degree is odd → the graph is not possible.

---

Quick Check

1. A graph has total degree 12. How many edges does it have?

2. Can a graph have total degree 9? Why or why not?

3. A tree has 6 vertices. What is the total degree?