9
$\begingroup$

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 ?

$\endgroup$
11
  • 1
    $\begingroup$ Does $A$ knowing $A$ count as one person that $A$ knows? $\endgroup$
    – cr001
    Commented Aug 16, 2020 at 6:44
  • $\begingroup$ No..$A $ knowing $A $ does not count as one person that $A $ knows $\endgroup$ Commented Aug 16, 2020 at 6:51
  • $\begingroup$ Then I think your argument "if $A$ and $B$ knows each other then they both know no one else" is flawed. $\endgroup$
    – cr001
    Commented Aug 16, 2020 at 6:53
  • $\begingroup$ Why...is that flawed $\endgroup$ Commented Aug 16, 2020 at 6:56
  • $\begingroup$ Image there are only three people $A, B, C$ know each other pairwisely, then $A$ and $B$ both know exactly one other person, namely $C$. $\endgroup$
    – cr001
    Commented Aug 16, 2020 at 6:58

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .