---
title: "Double Counting and Averaging"
summary: Count one set two ways, then compare — the source of the handshaking lemma, Turán-type bounds, and most "prove that m ≤ …" problems.
difficulty: hard
tags: [proofs, counting]
see: [foundations/types, special/degree-sequence]
---

:::idea title="The move"
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
:::theorem title="Handshaking, in its useful form"
$\sum_v \deg(v) = 2m$. Consequently $\delta n \le 2m \le \Delta n$, and $n\delta \le 2m \le n(n-1)$.
:::

:::proof
Count $S = \{(v,e): v \text{ is an endpoint of } e\}$. By vertices $|S| = \sum_v \deg(v)$; by edges $|S| = 2m$. ∎
:::

Everything below is that sentence with a different $S$.

:::example title="Bipartite graphs with no 4-cycle"
Let $G$ be $C_4$-free and bipartite with parts $A,B$, $|A| = n$. Count pairs $(v, \{a_1,a_2\})$ where $v$ is adjacent to both $a_1, a_2 \in A$: each pair $\{a_1,a_2\}$ has **at most one** common neighbour (two would make a 4-cycle), so $|S| \le \binom{n}{2}$. Each $v \in B$ contributes $\binom{\deg(v)}{2}$, so
$$\sum_{v \in B} \binom{\deg(v)}{2} \le \binom{n}{2}
\;\Rightarrow\; |B| \binom{\bar d}{2} \lesssim \tfrac{n^2}{2}
\;\Rightarrow\; m = \bar d\,|B| = O(n^{3/2}).$$
Two ingredients, both reusable: convexity of $\binom{x}{2}$ (Jensen) to replace the sum by the average, and "at most one" coming from a forbidden subgraph.
:::

:::example title="Euler's formula, counted twice"
In a simple planar graph with $n \ge 3$, count edge–face incidences: each face has $\ge 3$ edges, each edge borders $\le 2$ faces, so $3f \le 2m$. With $n - m + f = 2$ this gives $m \le 3n - 6$. (Full treatment: @special/planar.)
:::

:::example title="Average degree gives a short path"
If $m > \binom{k+1}{2}$ then some component has more than $k$ vertices of positive degree… Simpler and standard: if $\delta \ge 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(v_1) + \deg(v_\ell) \le |P|$ — a double count over the rotations, and the bound follows.
:::

## Averaging as a corollary
:::theorem title="Mean between min and max"
$\delta \le \frac{2m}{n} \le \Delta$, so some vertex has degree $\le \bar d$ and some has degree $\ge \bar d$.
:::

:::props title="What people then do with it"
- greedy colouring uses it $n$ times: every subgraph has a vertex of degree $\le \bar d$, so $\chi \le \lfloor \bar d_{\max}\rfloor + 1$ (degeneracy order, @special/coloring),
- independent set: some vertex has $\le \bar d$ neighbours, so $\alpha \ge \frac{n}{\bar d + 1}$ (Caro–Wei is the weighted version: $\alpha \ge \sum_v \frac{1}{\deg(v)+1}$),
- bipartite subgraph with $\ge 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,
- $K_{t}$-free bounds: replace "4-cycle" by "$K_t$" in the first example and you get the extremal number machinery of Turán.
:::

:::warning title="Choosing S is the whole problem"
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.
:::

:::problems
- [[CSES 1136]] Counting Paths | https://cses.fi/problemset/task/1136 | core | difference array on a tree
- [[CSES 1674]] Subordinates | https://cses.fi/problemset/task/1674 | easy | count the pairs (boss, subordinate)
:::