Assume $ m \lt n$ and call a graph with this property an $(m,n)$ graph. As you already know,

- A set of $k$ disjoint edges ( a
*one factor*) is a $(1,2k)$ graph.
- $k$ triangles sharing one common vertex (a
*windmill graph*) is a $(2,2k+1)$ graph.
- the
*complete graph* $K_{m+1}$ is an $(m,n)$ graph.

That is all the possibilities. For $m=1$ this is clear. For $m=2$ it is a theorem of Erdős, Rényi and Sós. That proof uses eigenvalue techniques, which is surprising for the simple conclusion. Other proofs have been given, none of them immediate. This paper includes a fairly simple proof along with a discussion of other proofs and more fruitful generalizations such as : " any pair of vertices has exactly $m$ common neighbors. "

Consider first $m=3.$ Let $G$ be a $(3,n)$ graph. Choose any three vertices $u,v,w.$ Their common neighbor $x$ has degree $d(x) \ge 3$. Consider $H$, the induced graph on these $d(x)$ vertices. It is a $(2,d(x))$ graph because for any two vertices $y,z \in H$, a common neighbor of $y,z$ in $H$ is the same as a common neighbor of $x,y,z$ in $G$, so there is exactly one. Furthermore, $H$ is a triangle since otherwise there would $t,q,r,s \in H$ with $t$ a common neighbor of $q,r,s.$ However we already have $x$ as the unique common neighbor of $q,r,s$ in $G$. Since $u,v,w$ are pairwise connected and were any three vertices, $G$ is a complete graph, $G=K_4$.

Now by induction, when $G$ is an $(m+1,n)$ graph for $ m \ge 3$, the induced graph $H$ on the neighbors of any vertex $x$ is an $(m,d(x))$ graph and hence $K_m$ meaning that $G$ is $K_{m+1}.$

commonneighbor" ? $\endgroup$ – joro Feb 7 '13 at 11:27