This problem is from the book Graph Theory by Bin Xiong. Although I tried to understand the authors answer, their explanation is unclear for me. The problem is as follows.

There are n people $A_{1}, A_{2}, ..., A_{n},$ taking part in a mathematics contest, where 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. Prove that the acquaintances of $A_1$ are as many as those of $A_2$.

The authors are proving the problem by denoting $n$ people by $n$ vertices and putting an edge between any two vertices if the corresponding two people know each other.

My questions are:

  1. I am wondering if there are some conditions which the problem statements lack. For example, if there are 3 people $A_{1}, A_{2}, A_{3}$ and suppose that $A_{1}, A_{3}$ know each other, the number of acquaintances of $A_1$ and $A_2$ does not seem to be same.

  2. And the authors are pointing out that there are no any 2 nonadjacent vertices which have 3 common neighbors. How could we infer this condition? Does the problem statements specify this condition explicitly?

  • 1
    $\begingroup$ I'd say you're right, there must be something missing. As stated, the only requirement is that two non-adjacent vertices share at least a common neighbor. In this you, you are right about 1), and you can find examples in which 2) does not hold. $\endgroup$ – Manuel Lafond Sep 24 '14 at 4:19
  • $\begingroup$ @bof I quoted the problem correctly. The problem statements should has a typo. Thank you. $\endgroup$ – MS.Kim Sep 26 '14 at 11:50
  • $\begingroup$ Doesn't make sense. Suppose everyone knows George, and there are no other acquaintanceships. Then any two who don't know each other have exactly one common acquaintance, namely, George. Seymour and George know each other, but George has many more acquaintances than Seymour has. $\endgroup$ – Gerry Myerson Sep 26 '14 at 12:54
  • $\begingroup$ Then please edit the question so it says what you mean to say. $\endgroup$ – Gerry Myerson Sep 26 '14 at 23:12
  • $\begingroup$ @bof, my (first) comment was meant to point out that the question didn't make sense; it wasn't directed at anything you wrote. $\endgroup$ – Gerry Myerson Sep 27 '14 at 6:17

If the condition "any two people who do not know each other would have common acquaintance" is strengthened to read "any two people who do not know each other have exactly two common acquaintances", then the statement is correct and has the following easy proof.

For $i=1,2$ let $\mathcal N_i$ be the set of all acquaintances of $A_i$ in $\{A_3,\dots,A_n\}$. By hypothesis $\mathcal N_1$ and $\mathcal N_2$ are disjoint. If $X\in\mathcal N_1$ then $X$ and $A_2$, who are not acquainted, have exactly two common acquaintances; one of then is $A_1$, the other one is in $\mathcal N_2$. Thus each member of $\mathcal N_1$ has exactly one acquaintance in $\mathcal N_2$, and vice versa. Hence $\mathcal N_1$ and $\mathcal N_2$ have the same number of elements, call it $k$, and so each of $A_1,A_2$ has exactly $k+1$ acquaintances.

More generally, if there is an integer $m\gt1$ such that any two nonadjacent vertices have exactly $m$ common neighbors, then any two adjacent vertices with no common neighbors have the same number of neighbors.


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.