Prove that if a graph has six vertices, then at least one of G or bar G has a subgraph isomorphic to K3 I think this proof is related to proving to Theorem on friends and strangers which can be proved with the pigeonhole principle. But I am at a loss as to what are the holes and pigeons in this case. I have tried many different graphs and they all work out to have a subgraph that is isomorphic to the K3.

See the youtube video on the subject posted by Numberphile here.
Theorem: A graph, G, with six or more vertices will always contain $K_3$ as an induced subgraph or its complement, $\stackrel{¯<!--\; ¯\; -->}{G}$, will contain $K_3$ as an induced subgraph.
The argument is as follows:
Suppose you have a graph, G, on six vertices. (The vertices may represent people, and edges between vertices represents that the two people are friends. We assume friendship is a symmetric binary relation)
Pick one of those vertices and call it v. Among the five other vertices one of the following two things will be true:
v has at least 3 neighbors
v has at least 3 non-neighbors
(seen easily from pigeon-hole principle)
Without loss of generality, assume it is the first case. Label three of v's neighbors as x,y,z. (There could be more than three neighbors, that is fine. We only need three for our purposes).
If it so happens that some two of v's neighbors are adjacent to eachother, for example x and y, then those two along with v form a $K_3$ in G and we have the result we were looking for. If that were not the case, then x,y,z form an independent set with no two of them being adjacent, in which case it follows that x,y,z form a $K_3$ in the complement graph, $\stackrel{¯<!--\; ¯\; -->}{G}$.
(the proof for the case where v has at least 3 non-neighbors is identical)
This is a special case of a much larger result called Ramsey's Theorem in a branch of mathematics what is known as Ramsey Theory. We define R(r,s) to be the fewest number of vertices such that a graph on at least that many vertices will always contain either a $K_r$ or the graph's complement will always contain a $K_s$. Our earlier work shows that the number $R(3,3)\le <!--\; \le \; -->6$. The pentagon acts as a counter example for 5 vertices showing that R(3,3)>5 and completes the proof that R(3,3)=6.
It has been proven that R(r,s) always exists and is finite for any finite r and s, though calculating the specific numbers is incredibly difficult. R(3,3) is one of the few simple cases we can prove exactly.
"Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens."
Several generalizations of this problem exist, where instead of working with the graph and its complement, we work with a coloration of the edges of the graph with an arbitrary number of colors (in the version of the problem discussed here, you could treat edges as "blue edges" and non-edges as "red edges"), or working with arbitrary subgraphs apart from just complete subgraphs. In each of these generalizations, it has been proven again that the number exists and is finite and we have upper bounds on the numbers, but is again frequently difficult to strictly determine. It is in contexts like these that numbers such as Graham's Number find its purpose.