The Handshaking Lemma

Problem : Show that, in any gathering of six people, there are either three people who all know each other or three people none of whom knows either of the other two (six people at a party).

Solution. To solve this problem, we draw a graph in which we represent each person by a vertex and join two vertices by a solid edge if the corresponding people know each other, and by a dotted edge if not. We must show that there is always a solid triangle or a dotted triangle.

Let v be any vertex. Then there must be exactly five edges incident with v, either solid or dashed, and so at least three of these edges must be of the same type. Let us assume that there are three solid edges (see figure 5) ; the case of atleast three dashed edges is similar.

If the people corresponding to the vertices w and x know each other, then v, w and x form a solid triangle, as required. Similarly, if the people corresponding to the vertices w and y, or to the vertices x and y, know each other, then we again obtain a solid triangle. These three cases are shown in Figure (6).

Finally, if no two of the people corresponding to the vertices w, x and y know each other, then w, x and y from a dotted triangle, as required (see figure (7).