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.
What a learner can do afterwards
- 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
1 · Read
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.
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.
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.
Name the graph precisely, count degrees with both hands per edge, and compare drawings by adjacency alone.
More to read
12.1 Graph Basics
A graph is vertices plus edges, each edge joining one or two vertices. Simple graphs allow at most one edge per pair and no loops. Multigraphs relax this with parallel edges and loops, while directed graphs give every edge an arrow.
Precision here pays off everywhere later. Loops contribute twice to degree, parallel edges multiply adjacency, and direction splits degree into in and out. Name the species before proving anything.
12.2 Graph Structures
The handshake lemma says the degrees sum to twice the edge count, since every edge shakes two hands. One immediate corollary: the number of odd degree vertices is even, because an odd sum of odds needs an even count.
This tiny parity fact kills many existence questions. No graph has exactly one odd vertex, and no simple graph on four vertices has degree sequence 3, 3, 3, 1.
12.3 Comparing Graphs
Two drawings show the same graph when vertices can be relabelled to preserve adjacency. Crossings, lengths and positions are accidents of drawing, not properties of the graph. Only the connection pattern counts.
To test sameness, match high degree vertices first and propagate constraints. Degree sequences give a quick necessary check: different sequences mean different graphs. Equal sequences invite a closer hunt for a relabelling.
12.5 Euler Circuits
Euler circuits tour every edge exactly once and return home. They exist exactly when the graph is connected (up to isolated vertices) and every vertex is even. The handshake parity resurfaces as the key condition.
Drawing puzzles like envelopes are Euler questions in disguise. Count the odd vertices: zero means a closed tour exists, two means an open trail, more means impossibility.
2 · Watch
Take it off screen
Where it sits
Learn first
Optional connections
17 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.