Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
At a meeting each delegate shakes hands with some of the others, never twice with the same person. The organiser wants every delegate to shake hands with exactly others.
Prove that this is impossible with delegates. Then show that it is possible with delegates by describing an arrangement, and find the number of handshakes in that case. Use the handshake lemma, and explain each step in words.
The degrees add up to twice the number of edges, so the number of odd vertices is even. has edges. A simple graph on vertices with more than edges is connected.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. The model. Delegates are vertices and handshakes are edges. Each delegate has degree .
Step 2. Fifteen delegates. The degrees add up to . By the handshake lemma this sum equals , which is even. But is odd. So the arrangement is impossible.
Step 3. Sixteen delegates. Split them into groups of , and let everyone shake hands with the other in their group. Each group is a copy of , so every delegate shakes exactly hands.
Step 4. Count. The degrees add up to , so there are handshakes. Each has edges, and agrees.
Answer: impossible for delegates; handshakes for . Proof complete.
Log in to join the discussion.
Loading…