Counting the Same Thing Two Ways

Some quantities are naturally counted two different ways — once by grouping one way, once by grouping another. Since both counts describe the same underlying set, they must come out equal. That equality, stated as an identity, is often the whole proof: no clever construction needed, just two honest tallies of one table.

Worked example: the handshake puzzle

At a party, some pairs of guests shake hands. Prove that the number of guests who shook an odd number of hands is always even.

Set up the table. Imagine a grid with one row per guest and one column per guest, and mark a cell whenever that row-guest shook hands with that column-guest. Each handshake between two people shows up as two marks in this table — one from each person's point of view.

Count by handshake. Every handshake contributes exactly 2 to the total count of marks in the table (once for each participant). So the total number of marks is $2H$, where $H$ is the number of handshakes — an even number.

Count by guest. Alternatively, sum each guest's own handshake count (their row total) across all guests. This sum is the same total number of marks, so it also equals $2H$ — even.

Compare. A sum of numbers is even exactly when the count of odd terms in it is even (each even term contributes nothing to the sum's parity, and odd terms must pair up to keep the total even). Since the sum of everyone's handshake counts is even, the number of guests with an odd handshake count must itself be even.

The same setup — a bipartite grid of people versus committees, or students versus clubs — proves things like "if every committee has an even number of members and every person sits on an even number of committees, then..." by counting person-committee marks by row and by column. It is also exactly why the sum of vertex degrees in any graph equals twice the number of edges: every edge is one mark from each of its two endpoints' perspectives.

The handshake identity is the same fact quants use when checking a trade blotter: total buy volume across counterparties must equal total sell volume, because every trade is one mark on each side of the ledger — a reconciliation break means the two counts of the same thing disagree.