Bondy's theorem

Remarks

Suppose that no such $x$ exists. Then for each $x \in X$ there are $i \ne j$ with symmetric difference $S_i \mathbin{\triangle} S_j = \set{x}$; join $S_i$ and $S_j$ by an edge labelled $x$. This gives a graph on the $n$ sets with $n$ edges, all with distinct labels, so it contains a cycle. Going around the cycle, the symmetric differences of the edges combine to $\emptyset$, but a symmetric difference of distinct singletons is not empty, a contradiction.

Example: $X = \set{1, 2}$ with $S_1 = \emptyset$ and $S_2 = \set{1}$. Removing $x = 2$ leaves $\emptyset$ and $\set{1}$, which are still distinct. The bound is sharp: for $X = \set{1, \ldots, n}$ the $n + 1$ sets $\emptyset, \set{1}, \ldots, \set{n}$ become non-distinct after removing any element $x$, since $\set{x}$ becomes $\emptyset$.

Going deeper

For a student

The theorem is a small result of extremal set theory with a short graph proof. It says that $n$ distinct rows of a $0$–$1$ matrix with $n$ columns stay distinct after deleting a suitable column. Its proof is a typical use of a graph to encode a family of sets.