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!
Best Answer
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.