Question : Consider a gathering of more than three people. Assume that knowing is a symmetric relation i.e., if person $A$ knows person $B$ then $B$ knows $A$. Given any two persons, number of people they both know is exactly one. Prove that if two persons do not know each other then they know the same number of people.
Now the given condition:
Given any two persons, number of people they both know is exactly one.
I think if $A $ and $B $ knows each other then they both know no one else and if they don't know each other then they both know only one another person let $C $.
I tried it to convert the problem to graph theory. Then according to the condition if $AB $ is joined then no other point is connected with both $A $ and $B $ and if $AB $ is not connected then they are both connected with only one other point.
But now I am unable to think how to prove. I drew the graph of 6 points ,but did not get something that will help me to prove.
Can you help me with this ?
Best Answer
This is really a graph theory problem, and I’ll talk about it in those terms: people are vertices, and vertices are adjacent (connected by an edge) if the corresponding people know each other. So we have a graph $G=\langle V,E\rangle$ with the property that for each pair of distinct $u,v\in V$ there is exactly one $w\in V$ adjacent to both $u$ and $v$; I’ll denote this vertex by $\varphi(u,v)$. Clearly this condition implies that $G$ is connected and does not contain a $4$-cycle. Moreover, $\deg v\ge 2$ for each $v\in V$: if $v$ is adjacent to $u$, it must also be adjacent to $\varphi(u,v)$. We want to show that if $\{u,v\}\notin E$, then $\deg u=\deg v$. For each $v\in V$ let $N(v)$ be the set of neighbors of $v$.
Suppose that $u,v\in V$ are not adjacent. Since $v\notin N(u)$, $\varphi(x,v)$ is defined for each $x\in N(u)$, and we can define a function
$$f_{uv}:N(u)\to N(v):x\mapsto\varphi(x,v)\,.$$
If $x,y\in N(u)$, $x\ne y$, and $f_{uv}(x)=f_{uv}(y)$, then $uxf_{uv}(x)yu$ is a $4$-cycle in $G$, which is impossible, so $f_{uv}$ is an injection. Of course $f_{vu}:N(v)\to N(u)$ is also an injection, so
$$\deg u=|N(u)|=|N(v)|=\deg v\,,$$
as desired.
It’s actually possible to characterize such graphs: they are precisely the friendship graphs. This result is Theorem $6$ of Paul Erdős, Alfréd Rényi, and Vera T. Sós ($1966$), ‘On a problem of graph theory’ [PDF], Studia Sci. Math. Hungar., $\mathbf{1}$: $215$-$235$. Relatively straightforward proofs can be found in Craig Huneke ($1$ January $2002$), ‘The Friendship Theorem’, The American Mathematical Monthly, $\mathbf{109}$ ($2$): $192$–$194$, doi:$10.2307/2695332$, [JSTOR $2695332$], and George B. Mertzios and Walter Unger ($2008$), ‘The friendship problem on graphs’ [PDF], Relations, Orders and Graphs: Interaction with Computer Science.