---
title: "Handshaking theorem; even number of odd vertices"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:handshaking-even-odd-degree-proof"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/handshaking-even-odd-degree-proof
site: BCT Engineering
---

# Handshaking theorem; even number of odd vertices

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Bhadra, 6 marks; 2068 Bhadra, 6 marks; 2075 Bhadra, 3 marks (asked 3 times)
- Video: [Proof: Every Graph has an Even Number of Odd Degree Vertices | Graph Theory](https://www.youtube.com/watch?v=M9rM0FADP-Q) — Wrath of Math
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/handshaking-even-odd-degree-proof
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

State the handshaking theorem for the undirected graph and use it to prove the theorem that an undirected graph has an even number of vertices of odd degree.

## Short answer

The handshaking theorem: sum of degrees = 2e. Proof of even number of odd-degree vertices: split vertices into even-degree and odd-degree sets. The sum of all degrees (2e) and sums from even-degree vertices are even, so the sum of odd-degree terms is even. Since each term is odd, the count of odd-degree vertices must be even.

## Answer

#### Handshaking theorem
If G = (V, E) is an undirected graph with e edges, then

**Σ over v ∈ V of deg(v) = 2e.**

Reason: each edge has two endpoints, so it adds exactly 1 to the degree of each of its two end vertices (a loop adds 2 to its single vertex). Counting all degrees counts every edge twice.

#### Theorem: an undirected graph has an even number of vertices of odd degree
**Proof.** Let V₁ be the set of vertices of even degree and V₂ the set of vertices of odd degree. By the handshaking theorem,

2e = Σ_{v∈V} deg(v) = Σ_{v∈V₁} deg(v) + Σ_{v∈V₂} deg(v).

1. 2e is even.
2. Σ_{v∈V₁} deg(v) is a sum of even numbers, so it is even.
3. Therefore Σ_{v∈V₂} deg(v) = 2e − Σ_{v∈V₁} deg(v) is even (difference of two even numbers).
4. Every term in this last sum is odd. A sum of odd numbers is even only if the number of terms is even.
5. Hence |V₂|, the number of vertices of odd degree, is even. ∎

Example: a graph with degrees 3, 3, 2, 2, 4 has 14 = 2·7 as degree sum, 7 edges, and two (even number) odd vertices.

## Check yourself

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

1. The handshaking theorem for a graph with e edges states:
   A. Sum of all vertex degrees = 2e
   B. Sum of all vertex degrees = e
   C. Sum of all vertex degrees = e/2
   D. Number of vertices = 2e
   Answer: A. The degree sum is twice the number of edges. (Key point: Handshaking statement)

2. Why does the degree sum equal 2e?
   A. Each edge adds 2 to every vertex
   B. Each edge adds 1 to the degree of each of its two endpoints
   C. Only odd vertices are counted
   D. Each vertex has exactly two edges
   Answer: B. Counting all degrees counts every edge twice, once at each end (a loop adds 2 to one vertex). (Key point: Reason)

3. In the proof, why is the sum of the degrees of even-degree vertices even?
   A. It equals 2e
   B. It equals the number of odd vertices
   C. It is a sum of even numbers
   D. It is a sum of odd numbers
   Answer: C. Adding even numbers always gives an even number. (Key point: Even-degree sum)

4. Why does the proof conclude the number of odd-degree vertices is even?
   A. Their degree sum is odd, so the count is even
   B. Each odd vertex pairs with an even vertex
   C. 2e is divisible by the number of vertices
   D. Their degree sum is even, and a sum of odd numbers is even only with an even count of terms
   Answer: D. 2e minus an even sum is even; since every term is odd, an even total needs an even number of terms. (Key point: Conclusion)

## Related in Discrete Structure

- [Short note: Handshaking theorem](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahandshaking-theorem-short-note) — Discrete Structure, chapter 4, asked 2×
- [Prove n even iff 7n+4 even](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aprove-n-even-iff-7n-plus-4-even) — Discrete Structure, chapter 1
- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×
- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×
- [Graph coloring and chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adefine-graph-coloring-chromatic-number) — Discrete Structure, chapter 4, asked 3×
- [Draw K6 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k6-chromatic-number) — Discrete Structure, chapter 4, asked 4×

## Related in other subjects

- [(4,3) even parity code is linear, odd parity is not](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aeven-odd-parity-linear-block) — Communication Systems, chapter 8
- [DFA: even a and odd b](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-even-a-odd-b) — Theory of Computation, chapter 2
- [RE: even a's followed by odd b's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-even-a-odd-b) — Theory of Computation, chapter 2
- [Count even and odd until -1](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Acount-even-odd-until-minus1) — Computer Programming, chapter 5