Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 2 / 17F / i / Solution

Fix any edge $xy$. After deleting $x$ and $y$, every nonempty subset $A$ of $X\setminus \{x\}$ satisfies $|\Gamma (A)\setminus \{y\}|\ge |A|$, by the strict inequality in the question. The Hall marriage theorem gives a matching in a graph for the remainder; adding $xy$ gives a matching covering $X$ and containing the prescribed edge. The case $|X|=1$ is immediate.