Chapter 1 · Graphs and Models
What a Graph Is, and How to Notice One
Vertices, edges, and the modelling habit that turns a scary statement into a graph problem.
A graph is a pair G = (V, E): a set of vertices and a set of edges, where each edge is a 2-element subset of V. That is the entire definition. Everything else in this chapter is bookkeeping.
Definition
The order is n = |V|, the size is m = |E|. The degree deg(v) of a vertex is the number of edges touching it; a vertex with deg(v) = 0 is isolated.
#The handshaking lemma
TheoremHandshaking
∑v ∈ V deg(v) = 2m. In particular, the number of odd-degree vertices is even.
Proof
Sum degrees by counting edges: each edge contributes exactly 1 to each of its two endpoints, hence 2 to the total.