Smallest number of people that can be invited at a party such that either $3$ of them met each other last year or $3$ of them did not?

Question

QUESTION: What is the smallest number of people that can be invited at a party this year such that either $3$ of them met each other last year or $3$ of them did not meet each other last year?

MY ANSWER: I know that this is a trivial application of Ramsey Theory, a subpart of which is also sometimes known as the Friendship Theorem.. And I know that this can be solved easily using a complete graph, to reach the answer $6$.. But what I am stuck with is a solution without using graph theory.. Here's how an official solution goes like-

(whatever is within the curly brace, $\{\}$, down below is understood)

Consider one of the people say $P$ in the party, and that he or she may or may not have met last year. Assume without loss of generality that $P$ met at least three of them last year : $A,B$ and $C$. $\{$ If any two of these met each other last year then those two and $P$ all met each other last year. Alternatively, none of $A,B$ and $C$ met each other last year.. $\}$

Now, I understand the ending.. But how can we even conclude from here that the answer is $6$ ??.. It seems from the solution that the answer is $4$, $(P,A,B,C)$. Also, how is the assumption in the 'without loss of generality' correct? .. It can always happen that $P$ has met exactly $2$ people last year.

While all the problem is solved using graph, that is a more clearer approach, I agree.. But what I wish to understand is how is this answer set up? Where am I thinking wrong that this solution seems contradictory to me? .. Can anyone explain this solution a bit more clearly?..

Thank you so much for your help and support.. :)

Answer 1

If $P$ didn't meet at least $3$ people from the party last year and there are a total of $6$ people, then $P$ knows less than or equal to $2$ people in the party and so there must exist a set of $3$ people each of whom $P$ did not meet last year. The argument then is exactly the same, except the meet/did not meet relations are flipped. Also, the proof above shows that if there are six people in the party, then the condition holds. It doesn't show that the answer is $4$ because in order to get a set of at least 3 people that P met/did not meet, you need $6$ people in total to apply the pigeonhole principle. To show that $6$ is the answer, one may demonstrate a set of five people where the condition fails to hold.

Answer 2

You have given the standard answer that proves that given six people at least three met or at least three did not meet last year. The other part is to show that you can have five people such that there is neither a group of three that met last year nor a group of three that did not meet. The easiest way is to show a complete graph with five vertices and color the edges red if the people met and blue if the people did not meet and not have a triangle of one color. If you draw the graph as a pentagon with diagonals, you can color the pentagon red and the diagonals blue.