I'm confused by this classic graph theory problem:
Suppose there are six people at a party. Prove that it is always possible to find either three people who all know each other, or three people none of whom knows either of the other two.
The wording seems ludicrous! What if one person knows all five of the others, but none of the others knows anyone but that one person who knows all the five? Or any other combination? All six know each other. All six came to a party, none knowing anyone else.
I've looked at other textbooks and they all seem to be similarly worded. It seems the wording should say at least somewhere. For example, if one person knows two to five others, and one of those knows another of that group, then you have the magic edge triangle of three. Likewise, if two to five others are mutual with one, but while you're trying to see if any of those knows another, if the answer is no for three, you get a . . . oh I'm lost! In general it seems to be saying there are either three or more mutual acquaintances, or, if not, than forces the situation to be three or more mutually strangers. What am I missing here?
Best Answer
You don't actually need to say "at least": Suppose that more than three people all know (or don't know) each other. Then, selecting any three of them, you have the triangle of people all knowing (or not knowing) each other.
To see that this is true, consider one person. Call him $A$ Because there are five other people at the party, $A$ must either know three of them, or not know three of them. Suppose, without loss of generality, that $A$ knows three of them (if there are instead three people he does not know, just switch the words "know" and "not know" in what follows). Now, if, among the three people that $A$ knows, any pair knows each other, we have a triangle of people who all know each other. However, if all of the people that $A$ knows do not know each other, then, because $A$ knows at least three people, we have a triangle of people who do not know each other.