3
$\begingroup$

50 mathematicians attend a conference at which each knows 25 other attendees. Show that you can select 4 of them who can then be seated at a round table, such that each person at the table knows the two people he or she is sitting next to.

I would like a hint please. I don't know how to get started.

$\endgroup$
  • 1
    $\begingroup$ This could be equivalently stated: Show that a 25-regular graph on 50 vertices contains a 4-cycle. Dirac's Theorem says you can actually find a cycle on all 50 vertices (also known as a Hamiltonian cycle). $\endgroup$ – Austin Mohr Oct 14 '14 at 0:17
  • $\begingroup$ @AustinMohr Thanks for the hint, but we haven't covered Dirae's Theorem or Hamiltonian cycles in my course so I don't think I am allowed to use them :P $\endgroup$ – Mathy Person Oct 14 '14 at 0:20
3
$\begingroup$

HINT: Start with two mathematicians who don’t know each other. Show that they must have at least $2$ acquaintances in common.

$\endgroup$
  • $\begingroup$ I've shown that, what should I prove now? $\endgroup$ – Yuna Kun Nov 19 '16 at 21:28
  • $\begingroup$ @YunaKun: Take those two mathematicians and two acquaintances whom they have in common, and seat those four people around a table in a suitable order. $\endgroup$ – Brian M. Scott Nov 19 '16 at 21:30
  • $\begingroup$ I see how that works, but aren't we assuming that if $A$ knows $B$, then $B$ knows $A$? I don't think the problem say that we could do that. $\endgroup$ – Yuna Kun Nov 19 '16 at 21:32
  • $\begingroup$ @YunaKun: Yes, we’re assuming that knows is a symmetric relation. That is the normal understanding. $\endgroup$ – Brian M. Scott Nov 19 '16 at 21:33
  • $\begingroup$ Okay, that makes more sense. Thanks! $\endgroup$ – Yuna Kun Nov 19 '16 at 21:34
0
$\begingroup$

Hint:

Select any vertex $u$ and any two of its neighbors $v$ and $w$. If we could find a common neighbor of $v$ and $w$ (other than $u$), then we would have a 4-cycle. Why do the high degrees of $u$ and $v$ guarantee that such a vertex exists?

$\endgroup$
0
$\begingroup$

Select two people, a and c, who don't know each other. The number of people who know a, plus the number of people who know c, is 50. However there are only 48 people in the group who are not a or c, so...

$\endgroup$
  • $\begingroup$ Hello! So if # of people who know a + # of people who know c = 50, and there are 48 people in the group who are not a or c, than a and c will have at least two people in common? And since knowing is mutual, the problem is solved? $\endgroup$ – Mathy Person Oct 14 '14 at 1:13

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.