---
title: "Short note: Handshaking theorem"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:handshaking-theorem-short-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/handshaking-theorem-short-note
site: BCT Engineering
---

# Short note: Handshaking theorem

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2072 Asoj, 4 marks; 2074 Bhadra, 2 marks (asked 2 times)
- Video: [Handshaking Theorem in Graph Theory | Imp for UGC NET and GATE](https://www.youtube.com/watch?v=Led6YwVxko0) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/handshaking-theorem-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on the Handshaking Theorem for undirected graphs (state the theorem).

## Short answer

The handshaking theorem: the sum of the degrees of all vertices in an undirected graph equals twice the number of edges (∑ deg(v) = 2e). Corollaries: the degree sum is even, there is an even number of odd-degree vertices, and a k-regular graph on n vertices has nk/2 edges.

## Answer

**Statement:** Let G = (V, E) be an undirected graph with e edges. Then the sum of the degrees of all vertices equals twice the number of edges:

**Σ_{v∈V} deg(v) = 2e**

This holds even with multiple edges and loops (a loop adds 2 to the degree of its vertex).

**Reason:** each edge connects two vertices (or one, for a loop), contributing 1 to each endpoint's degree, so each edge is counted twice in the sum.

**Corollaries:**
- The sum of the degrees is always even.
- The number of vertices of odd degree is even.
- A k-regular graph on n vertices has nk/2 edges.

**Example:** A graph with 5 edges has degree sum 10, for instance degrees 3, 3, 2, 1, 1 (four odd vertices, an even number). A graph on 4 vertices with degrees 3, 3, 3, 3 has 6 edges (K₄).

Directed version: the sum of in-degrees = sum of out-degrees = number of edges.

Use: checking whether a given degree sequence can be a graph; counting edges.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. The sum of degrees of all vertices in an undirected graph with e edges is:
   A. e
   B. e^2
   C. e - 1
   D. 2e
   Answer: D. Each edge is counted at both its endpoints. (Key point: Statement)

2. How does a loop affect the degree count?
   A. It adds 2 to the degree of its vertex
   B. It adds 1
   C. It adds 0
   D. It adds 2 to two different vertices
   Answer: A. A loop has both ends at the same vertex so the theorem still holds. (Key point: Loops)

3. Which is a corollary of the theorem?
   A. All degrees are even
   B. The number of odd-degree vertices is even
   C. The number of edges is even
   D. The number of vertices is even
   Answer: B. The degree sum is even, which forces an even number of odd terms. (Key point: Corollary)

4. Can degrees 3, 3, 2, 1, 1 form a graph with 5 edges?
   A. No: the sum must be 5
   B. No: four odd vertices is impossible
   C. Yes: degree sum 10 = 2 x 5 and four odd vertices is even
   D. Yes: but then it has 10 edges
   Answer: C. The sum is 10, so e = 5, and the count of odd vertices is even. (Key point: Use)

## Related in Discrete Structure

- [Handshaking theorem; even number of odd vertices](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahandshaking-even-odd-degree-proof) — Discrete Structure, chapter 4, asked 3×