Question

In a group of people, friendship is symmetric—that is, if person x is friends with person y then person y must also be friends with person x. Furthermore, no person is friends with themselves. Suppose there are exactly seven people in this group, and that every person has at least four friends. Prove that this group must contain three people who are all friends with each other.

Answer 1

Proof:

We will prove this, using graphs. Where the people are the nodes, and if two of them are friends that's an edge.

Now, let's take an arbitrary person A in our group of people. By hypothesis, our person A has at least 4 friends, then there are at most 2 people who are not friends of A. Let B one friend of A. We already know that B is friend of A, so B has at least 3 more friends, and one of them has to be also friend of A because there are only two people (at most) that are not.

Let C the friend of B who is also friend of A. We already know

• A is friend of B (because that's how we defined B)
• C is friend of A
• C is friend of B

Then A, B, C are three people who are all friends with each other.