Graph or complement contains complete graph


MHF Helper
Nov 2010
I am trying to prove that given any graph \(\displaystyle G\) on \(\displaystyle 4^n\) vertices, either \(\displaystyle G\) or its complement contains \(\displaystyle K_n\) (the complete graph on \(\displaystyle n\) 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).