# Graph theory mutual acquaintance and mutual strangers problem

Show that there is a gathering of five people in which there are no three people who all know each other, and no three people none of whom knows either of the other two.

There is a solution in the back of my book which I dont quite understand how they got and I would appreciate some insight on how to approach problems similar to these. Thanks!

-
fyi, this is an application of Ramsey theory. –  alancalvitti Feb 2 '13 at 20:15
@alan, it's an application of counting up to five. –  Gerry Myerson Feb 3 '13 at 0:00
...counting, and partitioning and identifying structure within partitions. Ramsey theory shows that structure can emerge from randomness. I thought the poster might like to know. –  alancalvitti Feb 3 '13 at 0:09

You want an example of $5$ people $-$ call them A, B, C, D, and E $-$ such that if you take any $3$ of them, some two of those $3$ do know each other, and some two of those $3$ do not know each other. Suppose that the following pairs know each other: A & B, B & C, C & D, D & E, and E & A. In other words, if you seat them around a table in alphabetical order, each of them knows his two neighbors and no one ele.

Now pick any $3$ people at that table. No matter which $3$ you pick, two of them will be neighbors, so they will know each other, and the third will not be a neighbor of at least one of the other two, so they won’t all three know one another.

The corresponding graph is just a $5$-cycle:

I arrived at this by starting with my five people represented by the vertices A through E below. Obviously I need some pairs who know each other, so I connected A and B with an edge to mark them as knowing each other. Now C, D, and E are a set of three, none of whom knows either of the others, so I need another edge there; I chose CD. Then I had to take care of A, D, and E, and for no particular reason I chose AE. I now had the ‘roof’ and ‘floor’ of the pentagonal ‘house’. Clearly I can’t have an edge BE, since then A, B, and E would all know one another. On the other hand, I still need an edge among B, E, and D, and one among B, E, and C as well. At that point I completed the pentagon and checked that it worked: given any three vertices, some two of the three are connected by an edge, and some two aren’t.

In short, my procedure wasn’t entirely systematic, but neither was it wholly random.

-
(A systematic approach begins by noticing no vertex can have degree $3$ or higher, and therefore cannot have degree $1$ or lower, so the graph must be $2$-regular. From this, one quickly arrives at the pentagon being the only possible arrangement.) –  Andres Caicedo Feb 2 '13 at 22:18
Thanks! That definitely helped explain the solution better than the textbook, it was the double negative that got me, thanks for clearing that up! –  DJ_ Feb 3 '13 at 0:25
@DJ_: You’re welcome. Do also take a look at Andres’ comment above yours, pointing out a systematic way of arriving at the same example. –  Brian M. Scott Feb 3 '13 at 0:33