The Party Handshake Puzzle

Definition A party has $n$ guests, where $n \ge 2$. Any two different guests either know each other or do not. Knowing is mutual, so if one guest knows another, the second also knows the first, and nobody counts themselves. The count of a guest is the number of other guests they know. The puzzle asks us to show that some two different guests always have the same count, whatever the acquaintances are. Each count is one of the $n$ numbers $0, 1, \ldots, n - 1$, since a guest can know at most the $n - 1$ others. The counts $0$ and $n - 1$ cannot both occur, because a guest with count $n - 1$ knows every other guest, so every other guest knows at least that one and has count at least $1$. The counts that occur therefore all lie among $0, 1, \ldots, n - 2$ or all among $1, 2, \ldots, n - 1$. That leaves at most $n - 1$ different values for $n$ guests, and by the pigeonhole principle two guests share a value. The same puzzle is often told with handshakes, where each pair of guests shakes hands at most once and each guest counts their own handshakes. It promises that some count is shared, not which one, and not that everyone has the same count.

Definition If $N$ objects are placed in $k$ boxes, where $N$ and $k$ are whole numbers with $N > k \ge 1$, then at least one box contains at least two objects. More generally, for any whole numbers $N \ge 1$ and $k \ge 1$, some box contains at least $\lceil N/k \rceil$ objects, where $\lceil x \rceil$ means the smallest whole number that is at least $x$. The reason is a count. If every box held fewer than $\lceil N/k \rceil$ objects, each would hold fewer than $N/k$, and the $k$ boxes together would hold fewer than $N$. The principle says that some box is shared, not which one, and when $N \le k$ it promises nothing, since every object could then have a box of its own.

Definition A simple graph consists of vertices and edges, where each edge joins two different vertices, any two vertices are joined by at most one edge, and edges have no direction. Two vertices joined by an edge are called neighbors, and the degree of a vertex is its number of neighbors. In a simple graph with $n$ vertices every degree is one of $0, 1, \ldots, n - 1$, because a vertex can be joined only to the other $n - 1$ vertices, and to each of them at most once. A party is a simple graph with the guests as vertices and an edge for each pair of guests who know each other, and the count of a guest is the degree of that vertex. The rules of the puzzle match the definition exactly. Mutual knowing means edges without direction, nobody counting themselves means no edge from a vertex to itself, and counting each pair at most once means at most one edge per pair.

Definition The degree sequence of a graph is the list of the degrees of its vertices, usually written from largest to smallest. The degree sequence of a simple graph with $n \ge 2$ vertices has three properties. Every entry is between $0$ and $n - 1$. The entries add up to twice the number of edges, since each edge adds $1$ to the degrees of both of its ends, so the sum is even and the number of odd entries is even. Finally, the entries $0$ and $n - 1$ never both appear. These conditions are necessary only. A list can have all three properties and still not be the degree sequence of any simple graph.

Definition Every simple graph with at least two vertices has two different vertices of the same degree. Both conditions matter. A graph with one vertex has no pair to compare, and when edges may repeat or have a direction, the degrees can all be different, as the example and the questions below show. The theorem guarantees at least one pair of equal degrees, but it does not say which degree repeats, and it does not say that all the degrees are equal. In fact, for every $n \ge 2$ there are simple graphs with $n$ vertices in which exactly two vertices share a degree and all the other degrees are different.