---
title: "Graphs, Degrees and the Handshake Lemma"
description: "Define a graph as a set of vertices with a set of pairs, and prove the first theorem about it: the degrees sum to twice the number of edges."
canonical: https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO
source: https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Graphs, Degrees and the Handshake Lemma

Define a graph as a set of vertices with a set of pairs, and prove the first theorem about it: the degrees sum to twice the number of edges.

Subject: Mathematics · Area: Discrete Mathematics · Ages 20 to 21
Page: https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO

## Ready when they can

- State what a graph is precisely, and distinguish simple graphs, multigraphs and directed graphs
- Prove the handshake lemma and deduce that the number of odd-degree vertices is even
- Decide whether two drawings represent the same graph

## Lesson: Graphs and the handshake lemma

A graph is a set of vertices with edges joining them. A simple graph allows at most one edge per pair and no loops. A multigraph allows parallel edges and loops, while a directed graph gives every edge an arrow.

**Example.** Name the species before proving anything. A loop joins a vertex to itself and counts twice toward its degree. Parallel edges multiply adjacency, and arrows split degree into in and out.

The handshake lemma says the vertex degrees sum to twice the edge count, since every edge shakes two hands. It follows that the number of odd degree vertices is even. Counting mod two kills many existence questions at once.

**Tip.** Two drawings show the same graph when vertices can be relabelled to preserve adjacency. Crossings, lengths, and positions are accidents of drawing. Match high degree vertices first, and use the degree sequence as a quick check: different sequences mean different graphs, while equal ones invite a hunt, like checking whether a four cycle realises all twos.

**Recap.** Name the graph precisely, count degrees with both hands per edge, and compare drawings by adjacency alone.

## Practice

17 questions on this page, each with its working shown.

## Needs first

- [Counting with the Product and Sum Rules](https://lightmysky.com/learn/mathematics/counting-with-the-product-and-sum-rules-mt_3NZC5F7RKP)
- [Graphs and How to Store Them](https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu)
- [Generating Functions](https://lightmysky.com/learn/mathematics/generating-functions-mt_WAX3O-HjRk)

## Opens up

- [Graph Colouring and Planarity](https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw)
- [Trees and Spanning Trees](https://lightmysky.com/learn/mathematics/trees-and-spanning-trees-mt_kMWpsz44yJ)