8
$\begingroup$

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all.

I suppose there is no one who is friend to all,I want to show that the graph with this assumption is strongly regular graph and then show that two parameters $f,g=\frac{1}{2}(n-1 \pm \frac{(n-1)(\lambda - \mu)+2k}{\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}})$ are not non negetive integers,my problem is when I suppose there is no one who is friend to all,I can't see that it is strongly regular graph.

of course this Idea was an help that was said in class,any other ideas will be great!

thanks.

something I must add is in this case every two adjacent or non-adjacent vertex has a common friends so $\lambda =\mu =1$ (if I am not wrong )now question is what is $k$? but it seems no matter what is $k$ ,because if $\lambda =\mu =1$ then $f=\frac{1}{2}n-\frac{1}{2}$ and it is not integer,I don't know what I am saying is right or wrong,please help me about this.

$\endgroup$
3
  • $\begingroup$ This situation can be represented as a graph with $n$ vertices such that for any pair of vertices, there exists exactly one path of length $2$ between them. If we show that this graph has the star $S_{n-1}$ as a subgraph then we are done. I think we can show that the graph is also a subgraph of the wheel $W_n$. $\endgroup$ Dec 23, 2014 at 13:50
  • $\begingroup$ @BrianM.Scott I thought about this some more, and I think the premise is only possible for odd $n$ (try $n=2$ or $n=4$). I think an induction on $\frac{n+1}{2}$ might work (adding two vertices in the inductive step). I think the graphs look like wheels with every other outer edge eliminated. $\endgroup$ Dec 23, 2014 at 14:13
  • 2
    $\begingroup$ This problem is well-known as the "friendship theorem". Google is your friend. $\endgroup$ Dec 23, 2014 at 17:28

1 Answer 1

3
$\begingroup$

The above problem is called Friendship Theorem for Erdos et al (1966), the prove is long. Here is the prove as stated in Bondy and Murty(2008)

enter image description here

$\endgroup$

You must log in to answer this question.

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