Let \[ \mathcal A=\{A_1,\ldots,A_n\} \] be a family of distinct subsets of an \(n\)-element set \(X\). Define a graph \(G\) on \(\mathcal A\) by joining \(A_i\) and \(A_j\) whenever \[ |A_i\triangle A_j|=1. \] If \(A_i\triangle A_j=\{x\}\), label the edge \(A_iA_j\) by \(x\).
Prove that there is a forest \(F\subseteq G\) whose edges use every label that occurs on an edge of \(G\). Deduce that there exists \(x\in X\) such that \[ A_1\setminus\{x\},\ldots,A_n\setminus\{x\} \] are all distinct.