In a group of 26 people, is it possible for each person to shake hands with exactly 3 other people?

Does anybody know how to solve this?

  • 2
    $\begingroup$ This is basically the question whether there exists a cubic graph with 26 vertices. A natural generalization is the question whether it is possible to construct a cubic graph for each even number of vertices - see this question: math.stackexchange.com/questions/412374/… (Handshake lemma easily implies that we cannot have a cubic graph with odd number of vertices.) $\endgroup$ – Martin Sleziak Apr 27 '14 at 9:04
  • $\begingroup$ I wonder whether this should be closed as a duplicate. (The other question is clearly more general.) $\endgroup$ – Martin Sleziak Apr 27 '14 at 10:31
  • $\begingroup$ @Did As you pointed out, my answer was wrong. I am abot to delete it. Thanks. $\endgroup$ – Jay Apr 28 '14 at 12:46

If you imagine forming a ring of all 26 people such that they form a regular 26-gon; then each person can shake hands with exactly three other people by shaking hands with the person opposite them and to either side of them.

Note that this is the case for any $n$-gon where $n\equiv 0\pmod{2}$ and $n>3$.

| cite | improve this answer | |
  • 5
    $\begingroup$ And it's also easy to prove that for an odd number of people, it's not possible for everyone to shake hands with exactly three other people (because the total number of shaken hands would have to be odd, but in each handshake two hands get shaken), therefore that condition is both necessary and sufficient. $\endgroup$ – celtschk Apr 27 '14 at 7:09
  • $\begingroup$ Perhaps you could post your construction as an answer to this more general question: math.stackexchange.com/questions/412374/… $\endgroup$ – Martin Sleziak Apr 27 '14 at 9:05

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.