STEP-BY-STEP LESSON · §4.9
Application: The Handshake Theorem
Connect the sum of degrees to the edge count.
Before you begin
The Language of Graphs
Vertices represent objects; edges represent selected connections. First specify directions and whether loops or parallel edges are allowed.
G=(V,E)
Adjacent vertices share an edge. In an undirected graph, degree counts edge ends at a vertex; a loop contributes two.
Direct Proof and Counterexample I: Introduction
Integer n is even iff there is an integer k with n=2k. Evenness gives this representation, and the representation gives evenness.
n even ↔ ∃k∈ℤ: n=2k
For “every odd integer has an odd square”, testing 3,5,7 suggests a pattern but leaves infinitely many cases. Write an arbitrary odd integer as 2k+1 with integer k; no special value is assumed.
n=2k+1; k∈ℤ
Symbols
- deg(v)
- degree of a vertex
- Σ
- sum
- |E| / |V|
- number of edges / number of vertices
Definitions and notation for this topic
Degree
deg(v)
In a simple undirected graph, the number of edges incident with a vertex.
In a graph allowing loops, a loop contributes 2 to the degree.
Separate glossary example
In A—B—C, deg(B)=2.
Step by step
Step 1 / 6
Count edge ends
In a finite undirected graph every edge has two ends. A loop also contributes two ends, both at one vertex.
Degree counts edge ends.
Worked example
Four people have handshake counts 1,2,2,1, with each handshake joining two different people. How many handshakes occurred?
- Add the personal counts: 1+2+2+1=6. This counts participation in handshakes.
- Each actual handshake contributes two participations, so divide by 2: 6/2=3.
- There are two odd counts, 1 and 1, which agrees with the theorem that the number of odd-degree vertices is even.
Optional self-check
Can exactly one vertex have odd degree?
Show answer
No, the number of such vertices must be even.