Mutual Friends

Prove that in any group of 6 people, there must be either a group of 3 people who are all mutual friends or a group of 3 people who are all mutual strangers. (Some assumptions: Friendship is symmetric — if I'm friends with you, then you're friends with me; and any two people are either friends or strangers.)

Without loss of generality, assume that there is a group of three people who are all friends with the first person. If any pair of them are mutual friends, then that pair plus the first person form a group of 3 mutual friends. If no pair are mutual friends, then that group of three people are all mutual strangers. The reverse argument holds if there is a group of three people all strangers with the first person.

Thus, either way there is a group of 3 people mutual friends or a group of 3 mutual strangers.

Person one could have six different numbers of friends:

If person one has 5 friends, then nobody else can be friends with each other without forming a group of three mutual friends (e.g. if 2 is friends with 3, then 1, 2, and 3 will be mutual friends), and if nobody else is friends with each other there will be five mutual strangers.

If person one has no friends, then nobody else can be strangers without forming a group of 3 mutual strangers, and if everybody else is friends with each other then there will be a group of five mutual friends.

If person one has one friend, then none of the four people that he is not friends with can be strangers, lest they form a group of three mutual strangers. And if everybody else is friends, then there is a group of four mutual friends.

If person one has two friends, then none of the three people that he is not friends with can be strangers with each other, or they will form a group of three mutual strangers. And if they are all friends, they form a group of three mutual friends.

The case of four friends is symmetric to the case of one friend, and the case of three friends is symmetric to the case of two friends (the same way that five friends is symmetric to no friends).

If there are 0 non-friended people (NFPs), there can only be (A) 3 mutually exclusive groups of 2 friends, or (B) 2 exclusive groups of 3 mutual friends, or (C) 1 group of 2 friends and another group of 4 mutual friends, or (D) all 6 are mutual friends. Each possibility means that there is either at least one set of 3 or more mutual friends (B, C, and D), or at least one set of 3 or more strangers to each other (A).

If there is 1 NFP, the remaining 5 must be either (A) 5 mutual friends, or (B) one pair of 2 friends and a separate group of 3 mutual friends. Either way, there is one group of at least 3 mutual friends.

If there are 2 NFPs, the remaining 4 must be either (A) 4 mutual friends, or (B) 2 pairs of friends. In case B, a set consisting of one person from each pair plus the NFP form a set of mutual strangers.

For 3, 4, 5, and 6 NFPs, there is, by definition, at least one set of 3 people who are strangers to each other, regardless of what pairings are available to the rest.

As for Brendon, I don't think his scenario is the "worst case," assuming that's a useful concept. Surely the worst case for mutual friendship is that everyone is mutual strangers, and the worst case for mutual strangership is that everyone is mutual friends? Brendon's "friendship in a ring" scenario is some intermediate stage -- one way of arranging people but not necessarily the hardest way to achieve three mutual friends or three mutual strangers.

Case(1) Suppose person A is friends with three people, B, C, and D. If any pair of B, C and D are friends, then that pair and A form a mutual admiration society. If no pair of B, C and D are friends, then they are a trio of mutual strangers.

Case (2) If A is friends with fewer than three of the others, than he is stranger to the rest, say D, E and F. If any pair of D, E and F are strangers, than that pair and A are mutually strangers. If no pair of D, E and F are strangers, then those three are the mutual friends.

All those people are my enemies. We're hardly friends or strangers.

Obviously, everybody corrected the miswording on their own. Did anybody do it subconsciously so that you didn't even notice there was a miswording?

Consider the most popular person (person with the most friends, in case of ties flip a coin). Assume that there is no group of 3 friends (completely connected subgraph with 3 vertices). Then there must be a group of three strangers as

if the most popular person has two or less friends then there will be at least 3 people that are strange to him. At least 2 of these three will also be strangers to each other by assumption (ie otherwise all 3 are friends). So there are 3 strangers (the most popular person and the 2 others he does not know).

If the most popular person has three or more friends then by assumption none of his friends know each other, and so must all be strangers, but there are at least 3 of them.

at leastthree mutual friends orat leastthree strangers.Did you?

Ramsey's Theorem stares, among other things, that R(m,n) is always finite. [That's m mutual friends, or n mutual strangers.] However, it is extremely hard to compute, even for small m and n. All we know is that 43 ≤ R(5,5) ≤ 49, for example.

See MathWorld for details.

The language of the question only asserts the existence of one of the two groups. One of these two groups may exist within a larger group for which the condition of complete "mutuality" is satisfied. For example, a group of 3 people who are all mutual friends exists in a group of 4 mutual friends.

Counterexample for 5:

A friends with E &B

B friends with A &D

C friends with E &D

D friends with C &B

E friends with A &C

or as a graph:

There are others.