Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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.) –  Martin Sleziak Apr 27 at 9:04
    
I wonder whether this should be closed as a duplicate. (The other question is clearly more general.) –  Martin Sleziak Apr 27 at 10:31
    
@Did As you pointed out, my answer was wrong. I am abot to delete it. Thanks. –  Jay Apr 28 at 12:46

1 Answer 1

up vote 24 down vote accepted

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$.

share|improve this answer
5  
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. –  celtschk Apr 27 at 7:09
    
Perhaps you could post your construction as an answer to this more general question: math.stackexchange.com/questions/412374/… –  Martin Sleziak Apr 27 at 9:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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