Problem:
In a group of nine people, one person knows
two of the others, two people each know four others,
four each know five others, and the remaining two each
know six others. Show that there are three people who
all know each other.
My Solution (asking for verification):
I want to show that we cant construct a graph with 9 vertices, obeying the given conditions, that does not include a subgraph with a cycle where 3 people all know each other.
If you have another solution, please tell me (I believe there is a much easier one).
Excuse my poor drawing skills with a mouse 😀
EDIT:I noticed, that the second step doesnt really minimize mutual friendship but the argument works the same after a few steps since we end up in the same position where we cant get further without creating that cycle!
Order a graph with 9 vertices from "knows the least" to "knows a lot of people"
Start to connect from left to right, "minimizing overlap in friendship."
Coming to the conclusion that from this point on we cant let the People(vertices) have more friends, because that would result in mutual friendship among 3 people.
I dont know if that is enough, would appreciate some help.
Im pretty sure there exists an easier answer but I really wanted to think about the problem in that way.
Best Answer
To start from the person who knows $2$ people, you have to consider who those $2$ friends are. They could have $4$ friends, $5$ friends, and $6$ friends, and while all of those cases lead to a triangle, you do have to consider all of them.
Start from a person who knows $6$ people instead: it's quicker, you don't have to do multiple steps, and you don't have to do casework on who is friends with whom.
If there is a friendship within that set of $6$ people, we're done. Otherwise, each of them is friends with at most $3$ people (the number outside the set). But there is only one person who's allowed to have fewer than $3$ friends; everyone else has at least $4$. Contradiction!