Per the title, let $G$ be a graph with at least two vertices, with the property that every two of its vertices have exactly two common neighbours.
Let $u, v$ be two vertices in $G$, and $g$ is a function which maps from the neighbourhood of $u$ to the neighbourhood of $v$. I assume you can show that $g$ is injective, so $\mathrm{deg}(v) \ge \mathrm{deg}(u)$, and then by symmetry $\mathrm{deg}(v) = \mathrm{deg}(u)$. So let $u, v$ be adjacent, and $w$ be a vertex that is adjacent to $u$. Then $g(w) = w$. Now, let $u, v$ not be adjacent, with $w$ still adjacent to $u$. If $v$ and $w$ are connected, $v, w$ have common neighbour $u$, and $g(w) = w$. If $v$ and $w$ are not connected, …?
I am unsure where to go from here. Any help would be much appreciated, thank you.
Best Answer
The trick is that we only look at adjacent vertices $v,u$. Because given the property of the graph, any two vertices of the graph are connected via two others, so the graph itself is connected. So if we proof that two adjacent vertices have the same degree, all vertices have the same degree.
So let $v,u$ be adjacent vertices and let $N(v)$ denote the neighborhood of $v$. For any $v'\in N(v)\setminus\{u\}$ there are two common vertices with $u$, one of them being $v$, because we established $v$ and $u$ are adjacent. Let's denote the other vertex by $u'$ and we have $u'\in N(u)\setminus\{v\}$. This gives rise to a map $g:N(v)\setminus\{u\}\rightarrow N(u)\setminus\{v\}$ with $g(v')$ mapping to the single element of $(N(v')\cap N(u))\setminus\{v\}$. Now if we take $v',v''\in N(v)$ and assume $g(v')=g(v'')$, that means that $g(v')\in(N(v'') \cap N(u))\setminus\{v\}$. So that means $g(v')$ ($\neq v$), which is by definition adjacent to $v'$ and $u$, is also adjacent to $v''$. And since $u,v',v''$ are adjacent to $v$, that would mean that $v$ and $g(v')$ would have at least three common neighbors if $v'\neq v''$, a contradiction. Hence $g$ is injective and therefore $\operatorname{deg}(v)\leq \operatorname{deg}(u)$, which leads to $\operatorname{deg}(v)= \operatorname{deg}(u)$ by symmetry, as you noted.