Generalized friendship theorem........ anyone has a proof to this one?

I don't get it. If three people have exactly one friend $X$, then won't four people have the exact same friend X? Because if four people have a common friend $Y \neq X$, then the three people in that set of four that have a common friend $X$ also have a common friend $Y$, contradicting that they have exactly one common friend. But this is obviously too easy for chinese TST.. am I missing something? --- (edit) oops: m is fixed, i get it.

Assuming the Friendship Theorem, it's easy to find the structure of such graphs (i.e. graphs in which every $m$ vertices have exactly one common neighbor). This is because amazingly enough, the problem gets easier when $m$ exceeds $2$ ($m=2$ is the classical version of the theorem). The graphs look like this: there are $m-1$ vertices $x_1,\ldots,x_{m-1}$, each of which is connected to all other vertices, and every other vertex has exactly one neighbor except for $x_1,\ldots,x_{m-1}$. We assume there are at least $m+1$ vertices, of course; otherwise the problem isn’t interesting, since the hypothesis is vacuously satisfied. In fact, it follows from this that all vertices must have degree $\ge m$. Otherwise we could find a common neighbor of a set formed by a vertex and all its neighbors. This common friend would have to be a neighbor of the vertex, and also of itself, but this ontradicts the fact that we do not consider a vertex to be a neighbor of itself. Suppose we’ve shown this for all values smaller than $m$ (for $m\ge 3$). Let $x_1$ be one of the vertices with maximal degree. We apply the induction hypothesis for $m-1$ to the graph induced on the set of neighbors of $x_1$. We will then find neighbors $x_2,\ldots,x_{m-1}$ of $x_1$, each of which is connected to all other neighbors of $x_1$. Because of the maximality assumption, the neighbors of $x_i$ are the neighbors of $x_1$ for all $i=\overline{1,m-1}$. Now let $x$ be a neighbor of $x_i$ different from all the $x_i$. Since $y,x_1,\ldots,x_{m-1}$ have exactly one common neighbor, $x$ is connected to exactly one other neighbor of $x_i$, so the graph $G$ induced on the set formed by $x_i$ and their neighbors has the form described two paragraphs above. Suppose now we can find a vertex $y$ not in $G$. Notice that there must be at least one neighbor $x$ of $x_i$ different from all $x_i$; otherwise $y,x_i$ can have no common friend. Take such a neighbor $x$. The vertices $x_1,\ldots,x_{m-2},x,y$ have exactly one common friend, and this friend can only be the unique neighbor of $x_i$ linked to $x$ (call it $\bar x$). Now repeat the procedure with $\bar x$ instead of $x$. We find that $y$ is linked to $x$ as well. But we now see that $y,x_i$ have at least two common friends ($x$ and $\bar x$), contradiction. This means that $x_i$ and their neighbors are all the vertices in the graph, and we have what we wanted.

grobber wrote: Assuming the Friendship Theorem, it's easy to find the structure of such graphs (i.e. graphs in which every $m$ vertices have exactly one common neighbor). This is because amazingly enough, the problem gets easier when $m$ exceeds $2$ ($m=2$ is the classical version of the theorem). The graphs look like this: there are $m-1$ vertices $x_1,\ldots,x_{m-1}$, each of which is connected to all other vertices, and every other vertex has exactly one neighbor except for $x_1,\ldots,x_{m-1}$. We assume there are at least $m+1$ vertices, of course; otherwise the problem isn’t interesting, since the hypothesis is vacuously satisfied. In fact, it follows from this that all vertices must have degree $\ge m$. Otherwise we could find a common neighbor of a set formed by a vertex and all its neighbors. This common friend would have to be a neighbor of the vertex, and also of itself, but this ontradicts the fact that we do not consider a vertex to be a neighbor of itself. Suppose we’ve shown this for all values smaller than $m$ (for $m\ge 3$). Let $x_1$ be one of the vertices with maximal degree. We apply the induction hypothesis for $m-1$ to the graph induced on the set of neighbors of $x_1$. We will then find neighbors $x_2,\ldots,x_{m-1}$ of $x_1$, each of which is connected to all other neighbors of $x_1$. Because of the maximality assumption, the neighbors of $x_i$ are the neighbors of $x_1$ for all $i=\overline{1,m-1}$. Now let $x$ be a neighbor of $x_i$ different from all the $x_i$. Since $y,x_1,\ldots,x_{m-1}$ have exactly one common neighbor, $x$ is connected to exactly one other neighbor of $x_i$, so the graph $G$ induced on the set formed by $x_i$ and their neighbors has the form described two paragraphs above. Suppose now we can find a vertex $y$ not in $G$. Notice that there must be at least one neighbor $x$ of $x_i$ different from all $x_i$; otherwise $y,x_i$ can have no common friend. Take such a neighbor $x$. The vertices $x_1,\ldots,x_{m-2},x,y$ have exactly one common friend, and this friend can only be the unique neighbor of $x_i$ linked to $x$ (call it $\bar x$). Now repeat the procedure with $\bar x$ instead of $x$. We find that $y$ is linked to $x$ as well. But we now see that $y,x_i$ have at least two common friends ($x$ and $\bar x$), contradiction. This means that $x_i$ and their neighbors are all the vertices in the graph, and we have what we wanted. How do you use induction hypothesis if $x_1,x_2,\ldots,x_{m-1}$ have two common neighbours ?

Another solution: Consider a graph $G$ where vertices represent the people in the wagon and edges their friendship relations. Let $x$ be the vertex with the largest neighborhood. Note $|\Gamma(x)|=n$. Obviously, $n \geq m$ (otherwise, there will be less than $m$ people in $G$ and the hypothesis is trivially satisfied) and we need to determine the value of $n$. Pick $m-1$ people from $\Gamma(x)$ and $x$. This $m$-tuple has exactly one common friend in $\Gamma(x)$ (since $x$ has neighbors only in $\Gamma(x)$). If a vertex $v \in \Gamma(x)$ has at least $m$ neighbors in $\Gamma(x)$, then these $m$ neighbors have two common friends in $G$, namely $x$ and $v$, contradiction. Hence, $v$ has at most $m-1$ neighbors in $\Gamma(x)$, which means that it can be the common friend of at most 1 $m$-tuple consisting of $m-1$ vertices in $\Gamma(x)$ and $x$. We have $\binom {n}{m-1}$ $(m-1)$-tuples in $\Gamma(x)$, hence: $$\binom {n}{m-1} \leq n \Longleftrightarrow$$$$\frac{n \cdot (n-1) \cdot \dots (n-m+2)}{(m-1)!} \leq n \Longleftrightarrow$$$$ (n-1) \cdot \dots (n-m+2) \leq (m-1)!$$If $n \geq m+1$, then: $$ (m-1)! \geq (n-1) \cdot \dots (n-m+2) \geq (m+1-1) \cdot \dots (m+1-m+2)=\frac{m!}{2} \Longleftrightarrow$$$$ m \leq 2$$which is rejected by hypothesis. Therefore $n \leq m$ and since $n \geq m$, we conclude $n=m$.