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
    Google told me that this question - with a solution - can be found in the book Graph Theory by Bin Xiong, Zhongyi Zheng on [page 5](http://books.google.com/books?id=FHkzyUeQ1MEC&pg=PA5). However, I still cannot find flaw in your counterexample, even after comparing it with their alleged proof. Perhaps they have forgotten to add some assumption?2011-10-08
  • 0
    You have found a counter-example, so what you have written here is wrong. For more guessing on the authors' intention, we would need more context.2011-10-08
  • 0
    http://meta.math.stackexchange.com/questions/2658/i-have-found-an-error-in-a-book-paper-what-do-i-do2011-10-08

1 Answers 1