Graph where any two vertices have unique neighbor in common must be regular.

Question

So, I was reading the first chapter of Van Lint's Course in Combinatorics and could not figure out this problem. Please help me and explain the solution in a simple manner.

Answer 1

Let $G = (V,E)$ be our graph. For $x \in V$, let $N(x) := \{ y \in V \big| (x,y)\in E\}$ be the neighborhood of $x$.
The hypothesis reads : for all $x\neq y \in V$, $N(x) \cap N(y)$ has exactly one element.

Question 1) Let $x,y \in V$ be such that $(x,y)\notin E$.

Let $v\in V$ be the unique vertex belonging to $N(x) \cap N(y)$. We have a function $f_{x,y} : N(x) \mapsto N(y)$ defined by : $$f_{x,y}(n) = \left\{ \begin{matrix} v & \textrm{if } n=v\\ \textrm{the only vertex of } N(n) \cap N(y) & \textrm{if } n \neq v \end{matrix}\right.$$

$f_{x,y}$ is injective

Indeed, let $m\neq n \in N(x)$. If we had $f_{x,y}(n) = f_{x,y}(m)$, then $N(n)\cap N(m)$ would have at least two distinct elements, namely $x$ and $f_{x,y}(n)$, a contradiction to our hypothesis!

Since $f_{y,x}: N(y) \mapsto N(x)$ is also an injection, we must have $|N(x)|=|N(y)|$, qed.

Question 2)
We need to show that $|N(x)| = |N(y)|$ for all $x, y \in V$.

(edit) the following isn't correct (how to find $z$?)

Let $x,y \in V$. If $(x,y) \notin E$, this follows from 1). Hence, we can assume that $x,y$ are connected. Since neither $x$ nor $y$ has degree $|V| - 1$, one can find $z \in V$ that is neither connected to $x$ nor to $y$. From 1), we get $|N(x)| = |N(z)| = |N(y)|$ qed.

A correct proof (credits to bof)
Take any $x_0 \in V$. Set $X := \{v \in V \big| d(x_0) = d(v)\}$. We need to show that $X = V$. Suppose not, then $Y := V \setminus X \neq \emptyset$.

Take $x\in X$ and $y \in Y$. Since $d(x)\neq d(y)$, $x$ and $y$ must be adjacent by point 1). Hence : $$\forall x \in X, \, \forall y \in Y, \, (x,y)\in E$$ If either $X$ or $Y$ had only one element, then this element would have $n-1$ neighbours, which can't be. Hence, $X$ and $Y$ have at least two elements each.

Let us take distinct elements $x_1\neq x_2 \in X$ and $y_1\neq y_2\in Y$. Since $x_i \in N(y_1) \cap N(y_2), \ i=1,2$ we must have $x_1 = x_2$, a contradiction!