# A graph logical task - Ramsey theory

I have the following puzzle and I want to check if the answers that I gave are correct. You can check also my reasoning behind the answers. The puzzle is:

In a perfect world two people are either friends or not friends. In this perfect world the population is exactly 6 people.

• In this perfect world a group of $$n$$ people is called completely friends when each person in the group is friends with every other person in the group.

• In this perfect world a group of $$n$$ people is called completely not friends when each person in the group is not friends with every other person in the group.

Which of the below statements are always true?

1. We can always find a group of 3 which is either completely friends or completely not friends.

2. If we have a group of 4 which are completely friends then the number of friendships is higher than the number of not friendships. (A friendship is when two people are friends. A not friendship is when two people are not friends.)

3. If we have a group of 3 which are completely not friends, there is no way for each person to be friend with exactly two others.

4. If we know that each two people have at least one common friend, then this means that we have a group of 4 which are completely friends.

5. There is no way for each two people to have exactly one common friend (from the other four).

6. There is no way for each two people to have exactly one common not friend (from the other four).

• This is basic graph theory, more math exercise than puzzle. #1 is true, #3 is false. I'll explain later, but you will get better answers sooner on Math.SE – Daniel Mathias May 20 '20 at 10:14
• Thanks, I found en.wikipedia.org/wiki/Theorem_on_friends_and_strangers which shows that for sure #1 is true. However, I have some problems to prove other stataments. – Try a May 20 '20 at 10:37
• A very nice reference. Counterexample for #3 is row 4, column 8. – Daniel Mathias May 20 '20 at 10:59
• A counterexample for #4 is the case where 2 out of the 6 (say, 1 and 2) are friends with everybody and there are no other friendships. Every pair that excludes 2 (1) has 2 (1) as a common friend, and 2/1 have every other person as common friends. But since 4/6 have only two friendships, there is no grouping of 4 complete friends. – H Rogers May 20 '20 at 12:08

TRUE

Reason:

Each person is either friends with atleast 3 people or not friends with atleast 3 people. You can draw graph among people to get better understanding yourself. In the example mentioned by you, 1, 3 and 5 are completely not friends with each other

FALSE

Reason

Correctly pointed out by you

FALSE

Reason

Let 1,2,3 be completely non friends. Let 1 be friends with 4 & 5, 2 with 4 & 6 and 3 with 5 & 6. Every one is friends with exactly 2 others. Note, here apart from 1,2,3, the group of 4,5 & 6 is also not completely friends with each other.

FALSE

Reason

Let 6 be common friend for any remaining pair(not involving 6 obviously). Now, let common friends of 1 & 6 be 2, 2 & 6 be 1, 3 & 6 be 2, 4 & 6 be 5 and 5 & 6 be 4. You will not find any group of four friends which are complete friends.

TRUE

Reason

https://en.wikipedia.org/wiki/Friendship_graph#Friendship_theorem It states that if a finite graph has the property that every two vertices have exactly one neighbour in common then there must be a vertex adjacent to everybody, and the graph is one of the so-called friendship graphs. In this case it means that we would need to have someone being friend with everybody. But for that we would need odd number of vertices