Show that it is possible to have a set of $5$ people such that there is no subgroup of $3$ strangers or a subgroup of $3$ people known to one another in the set.
I drew a little graph and came up with an example where there was no subgroup of $3$, either connected (people know each other) or disconnected (strangers). The problem said to show that this situation was possible. However, how do I use the pigeonhole principle for this? I'm sure I'm using it without even knowing, I just want to see how it is applied in this problem. Any solutions or hints are greatly appreciated.
There are two graphs that you consider. One is the acquaintance graph, and the other is a stranger graph. The two graphs are complement graphs. We know that there are $\binom{5}{2}=10$ total edges that may be split between these graphs. Let's call these $G_1,G_2$
Let $A$ be some node in the graph Each node has a total of 4 total edges incident on it. We can choose to split these edges in $G_1,G_2$ in either $\{1,3\}$ or $\{2,2\}$ ways.
If we split as $\{1,3\}$, then call the 3 adjacent nodes in $G_2$ to $A$ as ${B,C,D}$. Then none of ${B,C,D}$ can have edges in $G_2$ between themselves. If they do, they would form a triangle back to $A$. But this means they have edges between themselves in $G_1$. Thus they form a triangle or a 3-clique in $G_1$ violating the constraint.
Thus each node has $\{1,3\}$ edges incident on it in both $G_1,G_2$ (as the $\{1,3\}$ case was violated). Further, we have a total of 10 edges between $G_1,G_2$. Since the constraints are symmetric, the graphs may contain 5 edges each. Since each node contains 2 edges with a total of 5 edges, we get a 5-cycle.
A 5 cycle, happily turns out to be self complementary
EDIT: See here for details on how pigeon hole principle may be used in a related question of 6 people