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.
2 · Watch
Take it off screen
Where it sits
8 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.