The Double Counting Technique — Mathematics Knowledge System

Overview

Double counting (also called counting in two ways) is a proof technique that establishes an identity by counting the same finite set — usually a set of pairs or incidences — in two different ways and observing that both counts must agree. Rather than manipulating algebraic expressions, the technique sets up a table or bipartite relation between two collections of objects, sums along rows to get one expression, sums along columns to get another, and concludes the two expressions are equal because they count exactly the same total. It is one of the cleanest tools in combinatorics for proving identities, inequalities, and structural theorems (such as the handshake lemma) without induction or generating functions.

Intuition

Picture a rectangular grid of dots, where rows are elements of A, columns are elements of B, and a dot sits at position (a,b) exactly when a and b are related. Counting all the dots by going row by row gives one sum; counting them by going column by column gives another sum. Since both methods count the exact same dots, the two sums must be equal — that's the entire technique. The handshake lemma is the most famous instance: model a graph's edges as incidences between vertices and edges (each edge touches exactly 2 vertices), then counting (vertex, incident-edge) pairs by vertex gives the sum of degrees, while counting them by edge gives 2 for every edge, so the sum of all vertex degrees always equals twice the number of edges.

Formal Definition

Definition

Given a finite relation R between a set A and a set B (i.e. a subset of A × B, thought of as an 'incidence' between elements of A and elements of B), the size of R can be computed by summing over A or by summing over B:

|R| = \sum_{a \in A} |\{b \in B : (a,b) \in R\}| = \sum_{b \in B} |\{a \in A : (a,b) \in R\}|

Double counting identity

\sum_{v \in V} \deg(v) = 2|E|

Handshake lemma — the classic special case

Proofs

The Handshake Lemma: the sum of vertex degrees equals 2|E|

$\text{Let } P = \{(v,e) : v \text{ is an endpoint of edge } e\} \text{ be the set of vertex-edge incidences.}$ (Define the relation to be counted: which vertices touch which edges.)
$\text{Counting } P \text{ by vertex: for each } v, \text{ the number of edges touching } v \text{ is } \deg(v).$ (By definition, deg(v) is exactly the number of edges incident to v.)
$|P| = \sum_{v \in V} \deg(v)$ (Summing the per-vertex incidence counts over all vertices gives the total.)
$\text{Counting } P \text{ by edge: every edge has exactly 2 endpoints, contributing 2 incidences.}$ (An (undirected, simple) edge touches exactly 2 distinct vertices.)
$|P| = \sum_{e \in E} 2 = 2|E|$ (Summing the per-edge incidence counts (each edge contributes 2) over all edges gives the total.)
$\sum_{v \in V} \deg(v) = 2|E|$ (Both sums count the same set P, so they must be equal.)

Combinatorial proof of n·C(n-1,k-1) = k·C(n,k)

$\text{Count pairs (S, x) where S is a k-subset of an n-set and } x \in S \text{ is a marked element.}$ (Define the set of pairs (subset, marked member) to be counted two ways.)
$\text{Counting by choosing } S \text{ first: there are } \binom{n}{k} \text{ subsets, each with } k \text{ choices of marked element.}$ (For a fixed k-subset, any of its k elements can serve as the mark.)
$\text{Total} = k\binom{n}{k}$ (Multiply the number of subsets by the number of marks per subset.)
$\text{Counting by choosing } x \text{ first: there are } n \text{ choices for the marked element, then } \binom{n-1}{k-1} \text{ ways to complete } S \text{ from the rest.}$ (Fix the mark x among n elements; the remaining k-1 members of S come from the other n-1 elements.)
$\text{Total} = n\binom{n-1}{k-1}$ (Multiply the number of marks by the number of ways to complete the subset.)
$k\binom{n}{k} = n\binom{n-1}{k-1}$ (Both expressions count the same set of pairs (S,x), so they are equal.)

Properties

Handshake lemma

\sum_{v} \deg(v) = 2|E|

Absorption identity (proved by double counting)

k\binom{n}{k} = n\binom{n-1}{k-1}

General principle

\text{Any finite relation's size, summed by rows or by columns, gives the same total.}

Applications

Double counting bounds the number of edges in bipartite graphs used to model constraint-satisfaction and scheduling problems, and underlies the probabilistic-method's first-moment (expectation) arguments.

Worked Examples

By the handshake lemma, the sum of degrees equals 2|E|.
$3 + 1 + 2 + 2 = 8$
Divide by 2 to recover the edge count.
$|E| = 8 / 2 = 4$

Answer: 4 edges.

Practice Problems

Difficulty 3/10

A graph has 5 vertices, each of degree 4. How many edges does it have?

Difficulty 4/10

8 employees each sit on exactly 3 committees, and there are 6 committees total, each with the same number of members. How many members does each committee have?

Difficulty 6/10

Verify k·C(n,k) = n·C(n-1,k-1) for n=6, k=3 by computing both sides.

Common Mistakes

Common Mistake

Thinking double counting is just 'counting carefully twice' rather than a proof method.

Double counting is a specific proof technique: define ONE set of incidences (pairs), count its size two different structured ways (by rows, by columns), and conclude the two resulting expressions are equal because they count the same set.

Common Mistake

Forgetting that each edge contributes exactly 2 to the degree sum, leading to off-by-a-factor-of-2 errors.

An undirected edge has exactly 2 endpoints, so it is counted once in each endpoint's degree — hence sum of degrees = 2|E|, not |E|.

Quiz

The handshake lemma states that in any graph:

the number of vertices equals the number of edgesthe sum of vertex degrees equals twice the number of edgesevery vertex has even degreethe number of edges is always even

Double counting proves an identity by:

counting a set of objects and then counting it again to double-checkcomputing the same quantity via two different summation orders over a shared set of incidences, and equating the resultsusing induction on the size of the setconverting the identity into a generating function

Summary

Double counting proves identities by counting the same finite set of incidences in two different ways.
The handshake lemma is the classic instance: counting (vertex, incident edge) pairs by vertex gives ∑deg(v), by edge gives 2|E|, so they're equal.
The technique also proves algebraic identities like k·C(n,k) = n·C(n-1,k-1) via a marked-subset argument, with no algebra required.
It's a core tool of combinatorial proof, alongside bijective and induction arguments.

References

WebsiteWikipedia — Double counting (proof technique)