I am trying to figure out what the minimum number of vertices a graph must have in order guarantee that it has two triangles (3-cliques), two 3-independent sets, or one of each. Two cliques or independent sets are different if they differ by at least one vertex.
My initial thought is that the answer is 12, since Ramsey's theorem tells us that a complete graph with 6 vertices will have a 3-clique or a 3-independent set ($R(3,3)=6$). Combining two 6 vertex complete graphs will guarantee the existence of two 3-cliques or 3-independent sets. What I'm not sure of is whether this is the minimum or just an upper bound on the minimum.
Best Answer
Hint / Well known fact: Show that any complete graph on 6 vertices whose edges are colored with 2 colors has 2 monochromatic triangles.