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.

A graph with five edges Four vertices A, B, C and D joined in a square A–B–C–D–A, with one more edge, the diagonal from A to C. A and C have degree 3; B and D have degree 2. A B C D
A graph with five edges

In this graph the degrees are 3,2,3,23, 2, 3, 2, and they add to 1010: twice the 55 edges.

Why the degrees add to twice the edges

Count the “ends” of edges in two ways. Each edge has exactly 22 ends, so there are 2E2E 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:

∑vdeg⁡(v)=2E\sum_{v} \deg(v) = 2E

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

  1. How many edges does K6K_6 have?

    Answer

    1515

    Full solution

    6×52=15\tfrac{6 \times 5}{2} = 15.

  2. A graph has degrees 3,3,2,2,23, 3, 2, 2, 2. How many edges does it have?

    Answer

    66

    Full solution

    The degrees add to 1212, so E=6E = 6.

  3. Can a graph have degrees 3,3,3,3,33, 3, 3, 3, 3?

    Answer

    No

    Full solution

    The sum is 1515, which is odd.

  4. At a meeting, 1010 people each shake 44 hands. How many handshakes happen?

    Answer

    2020

    Full solution

    10×42\tfrac{10 \times 4}{2}.

  5. How many edges does a tree with 5050 vertices have?

    Answer

    4949

    Full solution

    A tree on nn vertices has n−1n - 1 edges.

  6. Every vertex of a graph with 88 vertices has degree 55. How many edges does it have?

    Answer

    2020

    Full solution

    8×52=20\tfrac{8 \times 5}{2} = 20.

  7. Can a graph have exactly one vertex of odd degree?

    Answer

    No

    Full solution

    The number of odd-degree vertices is always even.

  8. A student says the square-with-diagonal graph has 1010 edges, adding the degrees 3+2+3+23 + 2 + 3 + 2. What went wrong?

    Answer

    The degree sum counts every edge twice; there are 55 edges.

    Full solution

    Each edge contributes to two degrees, so E=102E = \tfrac{10}{2}.

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.

What to learn next