Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise

Question

Prove $G$ is regular if $d(u, v)$ is $x$ for adjacent $u$ and $v$ and is $y \ge 2$ otherwise.

Here $d(u, v)$ denotes the number of common adjacent vertices between $u$ and $v$.

PS: I've been working on a double counting method, but getting nowhere

Answer 1

I use the notations $V$ for the set of vertices, $E$ for the set of edges, $E(U)$ for the set of edges with both endpoints in $U\subset V$; $E(U_1,U_2)$ for the set of edges with one endpoint in $U_1$ and another in $U_2$, where $U_1,U_2$ are disjoint subsets of $V$; $N(v)$ for the set of vertices adjacent to $v\in V$.

Since the graph is connected (as follows from $y>0$), it suffices to prove that any two adjacent vertices $v,u$ have the same degree.

Denote $A=N(u)\cap N(v)$, $B=N(v)\setminus (A\cup \{u\})$, $C=N(u)\setminus (A\cup \{v\})$. Every vertex $w\in A$ has $x-1$ neighbors in $A\cup C$, summing over $w\in A$ we get $|A|\cdot (x-1)=2|E(A)|+|E(A,C)|$. Analogously, $|A|\cdot (x-1)=2|E(A)|+|E(A,B)|$. Therefore $|E(A,B)|=|E(A,C)|$. Each vertex in $B$ has $y-1$ neighbours in $A\cup C$, summing over all vertices in $B$ we get $(y-1)|B|=|E(A,B)|+|E(B,C)|$. Analogously, $(y-1)|C|=|E(A,C)|+|E(C,B)|$. Since $|E(A,B)|=|E(A,C)|$ and $E(B,C)|=E(C,B)$, we conclude that $(y-1)|B|=(y-1)|C|$, and $|B|=|C|$ (here we use that $y\geqslant 2$). It is equivalent to $u,v$ having equal degree.