We gonna have a party. We have 100 friends. And all of them have exactly 3 friends in that group of 100 people. But we don't know who is friend with who. And in our party there has to be at least 2 people who is friend with each other. How many people we should invite to be sure that there is gonna be at least 2 friends.
I have been looking for answer and came across with Ramsey Theory and Pigeonhole Theory. But I couldn't input my data to them.
We can think of a friendship graph. The vertices are the $100$ people and the edges represent a pair of friends. I am assuming friendship is mutual, that if C is friends with D, so is D friends with C. We are told it is a cubic graph, which means every vertex has three edges connected to it. We can turn the problem around by inviting everybody, then removing people from the room and asking what is the maximum number of people we can remove and guarantee that there are two vertices connected by an edge who are still in the room.
The total degree of the graph is $300$, so by the handshaking lemma there are $150$ edges. When we remove a person we delete at most three edges. It could be less if we have already deleted one or more edges from the last person we remove. This shows $n$ cannot be larger than $51$ because if we remove less than $50$ people there must be some edges left.
To show $n=51$ we can describe a graph that supports it. Split the people into groups $A$ and $B$ and number the people in each group from $1$ to $50$. Each person is friends with the person one number above them and one number below them in their own group (wrapping around at the end) and with the corresponding numbered person in the other group, so $A25$ is friends with $A24, A26, B25$. Now we can invite all the odd numbered people from group $A$ and all the even numbered people from group $B$, a total of $50$ and have no pair of friends.