Course contentsShow
← Mathematics
Lesson 2650 of 3,12153. Graph TheoryFree lesson

Degree of a Vertex and the Handshaking Lemma

Define vertex degree, state the handshaking lemma (sum of degrees equals twice the edge count), and prove it.

Degree of a Vertex and the Handshaking Lemma

What you'll learn: You'll understand how to measure a vertex's connections and why the sum of all vertex degrees in a graph always equals twice the number of edges.


The Degree of a Vertex

In graph theory, the degree of a vertex is simply the number of edges connected to it. Think of it like counting how many handshakes one person participates in at a party.

For example, if vertex v is connected to four edges, we write deg(v) = 4. In a directed graph, we distinguish between in-degree (incoming edges) and out-degree (outgoing edges), but for undirected graphs, we just count all incident edges.


The Handshaking Lemma

The Handshaking Lemma states:

The sum of all vertex degrees in a graph equals twice the number of edges.

Formally: If a graph G has vertices v₁, v₂, ..., vₙ and m edges, then:

Σ deg(vᵢ) = 2m


Proof

Why does this work? Each edge connects exactly two vertices. When we sum up all vertex degrees, every edge gets counted twice—once at each endpoint.

Imagine a party where people shake hands. Each handshake involves two people. If you ask everyone "How many handshakes did you participate in?" and add up all responses, you'll count every handshake twice (once per person involved). If there were 10 handshakes, the total count would be 20.


Corollary

An immediate consequence: The sum of degrees is always even. This means the number of vertices with odd degree must be even (you can't have just one vertex with odd degree in any graph).


Key Takeaway: The degree of a vertex counts its incident edges, and the Handshaking Lemma guarantees that summing all degrees gives exactly twice the edge count—because every edge touches two vertices.