2
$\begingroup$

I have taken the following problem from an introductory text on graph theory. Somehow I am missing something about this problem, as the statement seems wrong to me.

There is a group of $n$ people $A_1, \ldots,A_n$ in which some people know each other and any two people who do not know each other would have common acquaintance. Suppose that $A_1$ and $A_2$ know each other but do not have common acquaintance. Show that the acquaintances of $A_1$ are as many as those of $A_2.$

It is obvious how to model this question in the graph theoretical framework. What I am wondering is why isn't $P_3$ (picking a leaf and a 2-vertex for $A_1$ and $A_2$) a counterexample. The two leaf nodes do not know each other but have common friend, but $A_1$ and $A_2$ do not have the same number of acquaintances.

What am I missing?

  • 0
    http://meta.math.sta$c$kexchange.com/questions/2658/i-have-found-an-error-in-a-book-paper-what-do-i-do2011-10-08

1 Answers 1

1

From the link provided in the comment by Martin Sleziak, one can conclude from the proof that the authors wanted to demand that two nonadjacent vertices have exactly two common acquaintances.

  • 0
    I was just about to write a similar answer. (At least if Azoo has taken the problem from that book, it seems to be very reasonable conjecture.) Here's a [similar problem](http://www.mathkb.com/Uwe/Forum.aspx/math/33592/discrete-math-with-difficult-party) - it also contains the condition that non-adjacent vertices have exactly two common neighbors.2011-10-08