Discrete Math · Undergraduate
Graphs, Degrees and the Handshaking Lemma
Quick answer
A graph is a set of vertices joined by edges; it models friendships, road maps and computer networks. The degree of a vertex is the number of edges that meet it. Because every edge has two ends, the degrees always add up to twice the number of edges, the handshaking lemma, so the number of odd-degree vertices is always even. The complete graph on n vertices has n(n − 1)/2 edges, and every tree on n vertices has n − 1.
What you'll learn
- Describe a graph by its vertices, edges and degrees
- Prove and use the handshaking lemma
- Count the edges of complete graphs and trees
- Decide whether a degree list can belong to a graph
Dots and lines
A graph is a set of vertices joined by edges. People and friendships, cities and roads, computers and cables are all graphs. Only the connections matter: moving the vertices around the page gives the same graph.
The degree of a vertex is the number of edges that meet it. A path is a route along edges, a cycle is a path that returns to its start, and a graph is connected if every vertex can reach every other.
In this graph the degrees are , and they add to : twice the edges.
Why the degrees add to twice the edges
Count the “ends” of edges in two ways. Each edge has exactly ends, so there are ends in total. Each end sits at a vertex and counts once toward that vertex’s degree, so the degrees add up to the number of ends too. Counting the same thing two ways gives the handshaking lemma:
It is named for a party: if everyone counts the hands they shook, the total is twice the number of handshakes, since each handshake involves two hands.
A consequence: the number of vertices with odd degree is always even, since the degree sum is even.
Worked examples
Common mistakes
Practice problems
-
How many edges does have?
Answer
Full solution
.
-
A graph has degrees . How many edges does it have?
Answer
Full solution
The degrees add to , so .
-
Can a graph have degrees ?
Answer
No
Full solution
The sum is , which is odd.
-
At a meeting, people each shake hands. How many handshakes happen?
Answer
Full solution
.
-
How many edges does a tree with vertices have?
Answer
Full solution
A tree on vertices has edges.
-
Every vertex of a graph with vertices has degree . How many edges does it have?
Answer
Full solution
.
-
Can a graph have exactly one vertex of odd degree?
Answer
No
Full solution
The number of odd-degree vertices is always even.
-
A student says the square-with-diagonal graph has edges, adding the degrees . What went wrong?
Answer
The degree sum counts every edge twice; there are edges.
Full solution
Each edge contributes to two degrees, so .
Frequently asked questions
What is a graph in discrete math?
A set of vertices together with a set of edges, each edge joining two vertices. Only which pairs are joined matters, not where the vertices are drawn.
What is the handshaking lemma?
The sum of the degrees of all vertices equals twice the number of edges, because each edge adds 1 to the degree of each of its two ends.
Why is the number of odd-degree vertices even?
The degree sum is even. A sum of numbers is even only if it contains an even number of odd terms.
How many edges does a complete graph have?
Kₙ, in which every pair of the n vertices is joined, has n(n − 1)/2 edges.
How many edges does a tree have?
A tree, a connected graph with no cycles, on n vertices always has exactly n − 1 edges.