Graph or its Complement contains a triangle.

Question

How do I prove that the graph with at least 6 vertices or its complement contains a triangle?

Do I have to prove that if a graph contains a triangle, then its complement doesn't contain, and the opposite if its complement contains a triange then a graph doesn't?

Answer 1

So probably the reason this was tagged with 'ramsey-theory' is this section of the wikipedia page :

In the 2-colour case, an arbitrary simple graph G = (V, E) can be identified with the complete graph on the vertex set V whose edges are coloured with two colours (all the edges corresponding to those in E receive one colour and all the other edges receive the other colour.)

and then:

Conversely, it is possible to 2-colour a K5 without creating any monochromatic K3, showing that R(3, 3) > 5. The unique colouring is shown to the right. Thus R(3, 3) = 6.

Consider, for example the 6-cycle (C6). Obviously it has no triangles - now what is the complement of C6? Try drawing the complete graph on 6 vertices (K6) and coloring it with one color for C6 and another for the rest of the edges (the complement) - does this have a triangle?

Answer 2

It seems to be slightly easier to think about if you formulate it as

Color each edge in $K_6$ either red or green. Then there at least one triangle that is all red or all green.

(This is really the same as "arbitrary graph on 6 vertices", where "red" means an edge that's there and "green" means one that isn't -- but it makes it a bit easier to think about "edge is there" and "edge isn't there" as symmetric cases).

And a proof could go somewhat like:

• Choose three vertices $1$, $2$ and $3$. If the edges $12$, $23$ and $31$ all have the same color, then we're done. Otherwise let's say without loss of generality that $12$ and $23$ are red and $31$ is green.

• Now consider a fourth vertex $4$. If $14$ and $34$ are both green, then $134$ is a green triangle. So assume one of them is red. If $24$ is now red then $124$ or $234$ is a red triangle. So the only way not to have a valid triangle yet is if $24$ is green.

... and so forth.