I am trying to prove that given any graph on vertices, either or its complement contains (the complete graph on vertices) as a subgraph. I am tutoring students who have not had any graph theory, and they are supposed to approach the problem combinatorially (supposedly just applying the Pigeonhole Principle). Any idea what their instructor has in mind so I can give them a hint? They word the problem that given any set of 4^n people, there exists a subset of n people such that either any two of them know each other or no two of them know each other. (These sets of people are stalkerless, so if person A knows person B, then person B knows person A).