We conclude with an old puzzle that can be solved using a graph representation.

Eight people—four married couples—attend a dinner party. Various introductions are made; everybody shakes hands (once!) with some of the others. Of course,  no one shakes hands with his/her spouse.

After a while, the hostess asks every other person in the room, “how many times did you shake hands tonight?” It turns out that no two of the people she asked said that they shook hands the same number of times. (The hostess isn’t included of course; she didn’t ask herself.)

How many times had the host (the hostess’ spouse) shaken hands?

We use graph theory to represent the elements of the problem. Write W,X,Y,Z,  w,x,y,z for the eight people; W and w are one couple, X and x another, and so on.

We represent the party by a graph with people as vertices and handshakes as edges.

The number of handshakes is the degree of the vertex.

No one shook hands with more than six others (there are only six other people other than the two members of any couple). So the numbers of times people (other than the hostess) shook hands are seven different whole numbers, ranging from 0 to 6. It follows that each of 0, 1, 2, 3, 4, 5, 6 occurs exactly once among the degrees of those other than the hostess.

So somebody shook hands six times.

Let’s call this person X. He or she did not shake hands with his/her spouse x, so he/she shook with everybody else. These handshakes contribute the edges shown in the figure shown right:

Somebody shook hands 0 times. Looking at the figure, every vertex received at least one edge, except for x. (There might be further edges, not yet shown.) So x must be the person with no edges (no handshakes). No matter what happens, you will never add an edge touching x.

Now, somebody shook hands exactly five times. It was neither X nor x. Suppose it was Y. There is already one edge touching Y, the edge XY, so there are exactly four more edges touching Y. None of the new edges touch x or y (remember, people don’t shake with spouses). This implies that y is the only person to receive exactly only one: x has 0, and every other vertex has at least 2. The figure looks like the following (possibly with more edges):

Next, someone shook hands exactly four times. It cannot be X, x, Y or y; say it is Z. There are already two edges touching Z, and Z is not joined to z. So Z must be joined to W and w. We have obtained the following graph, showing all the handshakes:

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength