Graphs & trees

A graph is a set of vertices joined by edges, and it is the right model whenever things are connected: networks, maps, dependencies, social links. The single most useful fact is the handshaking lemma: the sum of all vertex degrees equals twice the number of edges, because every edge contributes one to the degree of each of its two endpoints. Worked example: a graph with vertex degrees 2, 3, 3, 2, 4, 2 has degree sum 16, so it has exactly 8 edges — and since the sum is even, such a degree sequence is at least possible. A tree is a connected graph with no cycles, and a tree on n vertices always has exactly n - 1 edges, which is why trees are the cheapest way to keep a network connected.