Chapter 4 · Proof Toolkit
Double Counting and Averaging
Count one set two ways, then compare — the source of the handshaking lemma, Turán-type bounds, and most "prove that m ≤ …" problems.
Pick a set S of pairs (vertex, edge), (vertex, path), (edge, face)… Count |S| by summing over the first coordinate, then over the second, and equate. Every inequality you can prove about one coordinate becomes an inequality about the other.
#The canonical instance
∑v deg(v) = 2m. Consequently δ n ≤ 2m ≤ Δ n, and nδ ≤ 2m ≤ n(n-1).
Count S = {(v,e): v is an endpoint of e}. By vertices |S| = ∑v deg(v); by edges |S| = 2m. ∎
Everything below is that sentence with a different S.
Let G be C4-free and bipartite with parts A,B, |A| = n. Count pairs (v, {a1,a2}) where v is adjacent to both a1, a2 ∈ A: each pair {a1,a2} has at most one common neighbour (two would make a 4-cycle), so |S| ≤ C(n, 2). Each v ∈ B contributes C(deg(v), 2), so
Two ingredients, both reusable: convexity of C(x, 2) (Jensen) to replace the sum by the average, and "at most one" coming from a forbidden subgraph.
In a simple planar graph with n ≥ 3, count edge–face incidences: each face has ≥ 3 edges, each edge borders ≤ 2 faces, so 3f ≤ 2m. With n - m + f = 2 this gives m ≤ 3n - 6. (Full treatment: Planarity and Euler's Formula.)
If m > C(k+1, 2) then some component has more than k vertices of positive degree… Simpler and standard: if δ ≥ 2 a cycle exists; if m > (k-1)n/2 then G contains a path on k+1 vertices. Proof: maximal path P; every neighbour of an endpoint lies on P; rotating P around its start (the classical rotation argument) yields deg(v1) + deg(v_ℓ) ≤ |P| — a double count over the rotations, and the bound follows.
#Averaging as a corollary
δ ≤ (2m)/(n) ≤ Δ, so some vertex has degree ≤ bar d and some has degree ≥ bar d.
What people then do with it
- greedy colouring uses it n times: every subgraph has a vertex of degree ≤ bar d, so χ ≤ ⌊ bar dmax⌋ + 1 (degeneracy order, Graph Colouring),
- independent set: some vertex has ≤ bar d neighbours, so α ≥ (n)/(bar d + 1) (Caro–Wei is the weighted version: α ≥ ∑v (1)/(deg(v)+1)),
- bipartite subgraph with ≥ m/2 edges: keep one side of a random partition, take expectation, or equivalently count the incidences (v, incident edge) and always place the smaller class,
- Kt-free bounds: replace "4-cycle" by "Kt" in the first example and you get the extremal number machinery of Turán.
If your count gives an equality you cannot bound in either direction, the set was wrong. The heuristic: S must be a relation between two very different-looking things (vertices vs edges, edges vs faces, paths vs pairs), and one of the two sums must be bounded by an obvious local argument (each edge has 2 ends; each pair has ≤ 1 common neighbour). If both sums are equally complicated, double counting will not help.