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?

  • $\begingroup$ 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. 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? $\endgroup$ – Martin Sleziak Oct 8 '11 at 9:20
  • $\begingroup$ 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. $\endgroup$ – Phira Oct 8 '11 at 9:21
  • $\begingroup$ meta.math.stackexchange.com/questions/2658/… $\endgroup$ – Martin Sleziak Oct 8 '11 at 9:43

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.

  • $\begingroup$ 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 - it also contains the condition that non-adjacent vertices have exactly two common neighbors. $\endgroup$ – Martin Sleziak Oct 8 '11 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.