There is a graph on $n$ vertices. Any $m$ distinct vertices of that graph,have exactly one common neighbor. Find all $(m,n)$ such that this kind of graph exists.

I guess that such a graph exists iff $m \mid n-1$. This is true by the friendship theorem for $m=2$ and it is easily seen to be true for $m= n-1$. But I don't have any plan of proof or construction of the graph for any other values of $m$. Also is it true, that if the graph exists, it is unique ? (Again true for $m=2$ and $m= n-1$ )

Thank you!

  • $\begingroup$ Do you mean "have exactly one common neighbor" ? $\endgroup$ – joro Feb 7 '13 at 11:27
  • $\begingroup$ Hi joro! Yes I mean common neighbor. Sorry for the mistake and thanks! $\endgroup$ – Bigcrow Feb 7 '13 at 12:00
  • $\begingroup$ I think if you want to generalize the friendship theorem, you have to see one of important parameter in its definition. In the definition of friendship graph, any two adjacent vertices have exactly one common neighbor. By your definition, you deleted this condition and it is not the generalization of friendship graph. $\endgroup$ – Shahrooz Janbaz Feb 7 '13 at 14:12
  • $\begingroup$ But for your problem, the graph has a dominating vertex and also the graph is $P_4$ free. $\endgroup$ – Shahrooz Janbaz Feb 7 '13 at 14:19
  • $\begingroup$ Let $A_m$ be the set of all graphs with $m$ vertices and that they have not dominating vertex. So, why the cone over any subset of $A_m$ is not an answer? $\endgroup$ – Shahrooz Janbaz Feb 7 '13 at 14:27

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}.$

  • $\begingroup$ Dear Aaron, did you assume that any $m$ adjacent vertices have exactly one common vertex as a neighbor? In the question, this assumption does not exist. Am I thinking truly? $\endgroup$ – Shahrooz Janbaz Feb 7 '13 at 22:02
  • $\begingroup$ I assumed that any $m$ distinct vertices (adjacent or not) have exactly one common neighbor. $\endgroup$ – Aaron Meyerowitz Feb 7 '13 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.