I came across the problem, to prove there exists a 3-clique on a graph G with 6 nodes or on its complement. I feel there could be some relation on the size of clique of a graph and its complement in general. Take the graph G, 1-2-3-4, for example, both of G and G' has maximum clique of size 2. And up to isomorphism, G is the unique tree with |V| > 1, s.t. G', its complement is also a tree.
Anyone knows any result which states a relationship of this kind?
Notice that the clique in the complement of $G$ is an independent set in $G$. So your question is equivalent to the following.
What is the largest number $k=k(n)$ such that all graphs on $n$ nodes have either a clique of size $k$ or an independent set of size $k$?
In other words, if we look at the complete graph $K_n$ and we color the edges for $G$ blue, and the edges for the complement red, we would like to know the maximum number $k$ such that there always exists a monochromatic clique.
These numbers are known as the Ramsey Numbers. The number $R(r,s)$ is the smallest integer such that the complete graph on $R(r,s)$ contains a blue clique on $r$ vertices or a red clique on $s$ vertices. Notice that this also holds for a complete graph on $n\ge R(r,s)$ vertices, just choose any (complete) subgraph on $R(r,s)$ vertices, then it holds there. So, the function $k$ above is given by $k(n)=\max(k':R(k,k)\le n\}$.
Finally, as you indicated in the question, we have $R(3,3)\le 6$, and in fact, even $R(3,3)=6$ as discussed in detail on Wikipedia.