Skip to main content
added te word "common"
Source Link

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!

There is a graph on $n$ vertices. Any $m$ distinct vertices of that graph,have exactly one 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!

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!

Source Link

Generalization of friendship theorem:n vertices, any m vertices have exactly one neighbor

There is a graph on $n$ vertices. Any $m$ distinct vertices of that graph,have exactly one 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!