Graphs: Prove that you can divide these people into 2 groups.

Question

Given a bunch of people, between each 4 of them one of these statements is true:

1. You can find 3 people who are friends with each other.
2. You can find 3 people that none of them is friends with another one.

Prove that these people can be divided into two groups such that in one of them everybody is friends with all other people and in the other no one is friends with another one.

Any hints to start the proof?

Answer 1

Hint: Divide them in two disjoint subset $A$ and $B$ such that the nodes in $B$ have no edges between them, and $B$ has the maximum cardinality among the sets made this way (called indipendent sets). Prove that $A$ is totally connected (a clique) and you're done.

Answer 2

The statement you are asking to prove is false.

Consider seven people, labelled A through G, such that the friendships are $$ (A,B), (A,C), (B,C), (D,E) $$ that is, there is a triplet of mutual friends, a pair of friends, and a pair of loners. This set satisfies the two given conditions, based on $(A,B,C)$ for the first and $(E,F,G)$ for the second.

Assume the set can be split into a group of mutual frieds and a group of mutual non-friends. Then the group of mutual friends must include at least one among D and E (since if both are ijn the group of non-frieds, that violates the non-frieds condition. Similarly, the group of mutual friends must contain at least among of A, B, and C. But since no person among A, B, and C is a friend with D or E, the group of friends does not have a complete mutual friendship relation.